0
Какова временная сложность этого уравнения?
Ответ 2^n, но я не могу найти решение.временная сложность этого уравнения t (n) = t (n-1) * t (n-1)
t(n)=t(n-1)*t(n-1)
A
ответ
2
Предполагая, что базовый случай некоторая конечная константа, она должна работать в O(2^n), так как для каждого вызова, он запускает два рекурсивных вызовов.
Например, если базовый случай t(1) = constant
t(1) = t(0) * t(0) = constant * constant
t(2) = t(1) * t(1)
t(1) = t(0) * t(0) = constant * constant
t(1) = t(0) * t(0) = constant * constant
t(3) = t(2) * t(2)
t(2) = t(1) * t(1)
t(1) = t(0) * t(0) = constant * constant
t(1) = t(0) * t(0) = constant * constant
t(2) = t(1) * t(1)
t(1) = t(0) * t(0) = constant * constant
t(1) = t(0) * t(0) = constant * constant
Это может, однако, быть уменьшена до O(n) за счет кэширования значения (не предполагая побочных эффектов)
t(1) = t(0) * t(0) = constant * constant
t(2) = t(1) * t(1)
t(1) = t(0) * t(0) = constant * constant
t(1) evaluated in constant time cache lookup
t(3) = t(2) * t(2)
t(2) = t(1) * t(1)
t(1) = t(0) * t(0) = constant * constant
t(1) evaluated in constant time cache lookup
t(2) evaluated in constant time cache lookup
+0
thanks.is есть другое решение, решая это уравнение: t (n) = t (n-1)^2 – user123
+0
Само уравнение не является «разрешимым», это скорее рекуррентное отношение. Определение верхней границы в основном определяется тем, что для произвольного n t (n-1) вызывается дважды и в каждом вызове t (n-1) t (n-2) называется дважды [t (n-2)) называется 4 раза] и t (n-3) и т. д. – arcyqwerty
+0
Если вы ищете доказательство, вы можете, вероятно, вывести его, используя доказательство по индукции, но поскольку его довольно просто, вам нужно будет рассуждать, что если каждый бросок t (n) приводит к 2 вызовам t (n-1), тогда будут вызовы O (2^n) для t – arcyqwerty
Смежные вопросы
- 1. Какова временная сложность T (n) = (T (n-1) + n!)?
- 2. T (n) временная сложность для вложенных циклов
- 3. сложность функции T (N) = T (n/2) + 2^n
- 4. Сложность времени алгоритма T (n)
- 5. Сложность повторения T (n) = T (n-2) + 1/lgn?
- 6. Почему худшая временная сложность этого простого алгоритма T (n/2) +1 в отличие от n^2 + T (n-1)?
- 7. Сложность рекурсии: T (n) = T (n-1) + T (n-2) + C
- 8. Как удалить \ n, \ t из слова, например "\ n \ t \ t \ t \ tDay недели \ n \ t \ t \ t"?
- 9. Получите сложность T (n) = T (n/4) + T (3n/4) + c
- 10. Решение рекуррентного отношения T (n) = T (n-1) * T (n-2) + c, где T (0) = 1 и T (1) = 2
- 11. Как решить рекурсивную сложность T (n) = T (n/3) + T (2n/3) + cn
- 12. Как решить рекурсивную сложность T (n) = T (n/4) + t (3n/4) +1?
- 13. Анализ алгоритма с повторением T (n) = T (n - 1) + T (n - 2) + T (n -3)?
- 14. Учитывая «T, общее число» и «N, количество дней», как разделить T на N так, чтобы n1 + n2 ... равнялось T в экспоненциальной кривой?
- 15. Алгоритмическое T (n) = T (n-1) +2
- 16. Как решить это уравнение сложности, T (n) = T (n-3) + T (n-5)
- 17. Python: скрипт извлекает ошибки: u '\ n \ t \ t \ t \ t \ t \ t'
- 18. Действительно ли T (n)> = T (n-1) истинно?
- 19. Как решить рекурсию T (n) = T (n/2) + T (n/4), T (1) = 0, T (2) = 1 есть T (n) = Θ (n lg φ) , где φ - золотой коэффициент?
- 20. Вычислительная сложность в формате T (n) = Θ
- 21. Какова оценка или T (n) этого алгоритма?
- 22. Какова асимптотическая сложность T (n) = T (n-1) + O (n * n!)?
- 23. Как читать из xml-файла без/n/t/t myValue \ n \ t \ t
- 24. Сжатие {| n1, n2 | n1^n2} в Ruby
- 25. Как решить T (n) = T (n-1) + n^2?
- 26. Что такое сложность выполнения, если T (n) = n * T (n-1)?
- 27. Как решить уравнение рекурсии T (n) = T (n/2) + T (n/4) + \ Theta (n)?
- 28. Ищите строки, содержащие «\ N \t \t абвг»
- 29. Как решить рекуррентность T (n) = T (n-1) + ... T (1) +1?
- 30. Решите T (n) = T (n-1) + n^4 методом замещения
Было бы O (2 ** n) если плохо реализовано. – Hyperboreus
Разве это не логарифмическая идентичность? –