Это проблема из моей домашней работы. Я не совсем уверен, как решить такую проблему.Домашнее задание: Big-Oh для рекурсивных функций
If T(n) = nT(n - 1) and T(1) = 3, then
a) T(n) = O(n^n)
b) T(n) = Ω(n!)
c) T(n) = O(2^(nlogn))
d) none of the above
Мне не нужен точный ответ на этот вопрос (с его домашней работы), но я хотел бы знать, как сказать границу рекурсивной функции.
Просто попробуйте работать через него. Предположим, что n = 3. Сколько итераций будет? Как насчет n = 4? Как быстро увеличивается количество итераций при увеличении n?
Другой способ взглянуть на это: В формуле, как функция «ветвь»? линейные функции не ветвятся, они имеют простую рекурсию 1: 1. Экспоненциальные функции будут разветвляться несколько раз. Логарифмические функции ветви, но уменьшить сложность данных они работают на ... и т.д.
For n = 4:
T(4) = 4 * T(4-1)
T(3) = 3 * T(3-1)
T(2) = 2 * T(2-1)
T(1) = 3
Время выполнения на 2 шага для каждого вызова (умножение и рекурсивного вызова). Для данного примера, для 4 звонков у вас будет 8 шагов которые линейно исполненных (вы не имеете комбинаторный или логарифмическую алгоритма, так что ваша функция ограничена на О (п).
Для возможных вариантов у вас есть ответы будут:.
a) T(4) = O(4^4) -> 256
b) T(4) = Ω(4!) -> 24
c) T(4) = O(2^(4log4)) ~> 5.27
d) none of the above
Таким образом, ваш выбор должен быть d надеется, что это поможет
Привет, спасибо за ваш ответ =) просто задайте небольшой вопрос, можете ли вы дать мне рекурсивную функцию, которая имеет «O (nlogn)» или «O (logn)»? Спасибо –
Конечно, для O (nlogn) Быстрое преобразование Фурье, heapsort, quicksort, сортировка слияния или f (x) = n + log (n)! для O (logn) - двоичный поиск в отсортированном массиве или любую операцию в биномиальной куче и вычисление последовательности Фибоначчи с матричным умножением. Проверьте wiki о них, они дают отличные объяснения всем алгоритмам. –
достаточно просто понять –
Я не 100% уверен, что в первой части вы упомянули взять мой вопрос, как пример, когда '... n = 3' Я знаю, что будут такие вызовы функций, как this 'T (1) => (return result to) 2T (2-1) => 3T (3-1)', но как определить bo и от чего? –
Итак, вы определили, что будет 3 итерации, когда 'n = 3'. Как насчет 'n = 4'? Можете ли вы предсказать для 'n = 5'? – Amadan
Я думаю, что есть 4 итерации, когда 'n = 4' и' n = 5' есть 5 итераций? но если это так, то не будет «O (n)»? –