Какова временная сложность следующей рекурсивной функции:
|
(А) (П)
(В) (NlogN)
(С) (LOGN)
(D) (Loglogn)
(А) А
(Б) Б
(С) С
(D) D
Ответ: (Д)
Объяснение: Рекурсивное отношение для DoSomething ()
T(n) = T() + C1 if n > 2
Мы проигнорировали часть floor (), так как здесь не имеет значения, пол это или потолок.
Let n = 2^m, T(n) = T(2^m) Let T(2^m) = S(m) From the above two, T(n) = S(m) S(m) = S(m/2) + C1 /* This is simply binary search recursion*/ S(m) = O(logm) = O(loglogn) /* Since n = 2^m */ Now, let us go back to the original recursive function T(n) T(n) = S(m) = O(LogLogn)
Рекомендуемые посты:
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 11
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 11
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 9
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 4
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 1
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 6
- Алгоритмы | Анализ алгоритмов (рецидивов) | вопрос 2
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 11
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 3
- Алгоритмы | Анализ алгоритмов (рецидивов) | Вопрос 7
- Алгоритмы | Анализ алгоритмов | Вопрос 8
- Алгоритмы | Анализ алгоритмов | Вопрос 1
- Алгоритмы | Анализ алгоритмов | Вопрос 9
- Алгоритмы | Анализ алгоритмов | Вопрос 10
- Алгоритмы | Анализ алгоритмов | Вопрос 15
0.00 (0%) 0 votes