Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 39

Предположим, что существует ⌈ log n orted отсортированных списков из ⌊ n / log n ⌋ элементов каждый. Временная сложность создания отсортированного списка всех этих элементов:
(Подсказка: используйте структуру данных кучи)
(A) O (n log log n)
(B) θ (n log n)
(C) Ω (n log n)
(D) Ω (n3 / 2)

Ответ: (А)
Объяснение: Мы можем объединить массивы x каждого размера y in за O (xy * Logy), используя Min Heap.

x = n / Logn
у = логн

Мы получаем O (n / Logn * Logn * Log Log n), который является O (nLogLogn)
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2005 | Вопрос 39

0.00 (0%) 0 votes