Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 25

N элементов хранятся в отсортированном двусвязном списке. Для операции удаления предоставляется указатель на удаляемую запись. Для операции нажатия клавиши указатель предоставляется на запись, над которой должна быть выполнена операция. Алгоритм выполняет следующие операции над списком в следующем порядке:
Θ (N) удалить, O (журнал N) вставить, O (журнал N) найти и Θ (N) клавиша уменьшения

Какова временная сложность всех этих операций вместе взятых
(A) O (Log 2 N)
(B) O (N)
(С) O (N 2 )
(D) Θ (N 2 Log N)

Ответ: (с)
Объяснение: Временная сложность операции уменьшения клавиши составляет Θ (1), так как у нас есть указатель на запись, где мы должны выполнить операцию. Тем не менее, мы должны сохранить отсортированный двухсвязный список, и после операции уменьшения ключа нам нужно найти новое местоположение ключа. Этот шаг займет Θ (N) времени, а поскольку есть Θ (N) операций с клавишей уменьшения, сложность времени становится O (N ²).

Обратите внимание, что остальные три операции имеют нижнюю границу, чем эта.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 25

0.00 (0%) 0 votes