Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 41

Если мы используем Radix Sort для сортировки n целых чисел в диапазоне (n k / 2 , n k ], то для некоторого k> 0, который не зависит от n, потребовалось бы время?
(A) Θ (n)
(B) Θ (кн)
(C) Θ (nlogn)
(D) Θ (n 2 )

Ответ: (с)
Пояснение: Сложность времени сортировки по корням = O (wn)
для n ключей размера слова = w

=> w = log (n k )

O (Wn) = O (klogn.n)

=> kO (nlogn)
Тест на этот вопрос

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

ВОРОТА | Gate IT 2008 | Вопрос 41

0.00 (0%) 0 votes