Рубрики

Алгоритмы | Сортировка | Вопрос 14

В модифицированной сортировке слиянием входной массив разделяется на одну треть длины (N) массива. Что из следующего является самой жесткой верхней границей временной сложности этой модифицированной сортировки слиянием.
(A) N (logN основание 3)
(B) N (logN основание 2/3)
(C) N (logN основание 1/3)
(D) N (logN основание 3/2)

Ответ: (Д)
Пояснение: Сложность времени определяется как:
Т (Н) = Т (Н / 3) + Т (2Н / 3) + Н
Решение приведенного выше рекуррентного соотношения дает, T (N) = N (logN base 3/2)
Тест на этот вопрос

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

Алгоритмы | Сортировка | Вопрос 14

0.00 (0%) 0 votes