1
Возникает вопрос:Решение Т (п) = √2 * Т (п/2) + журнал п, используя теорему мастер
T(n) = √2*T(n/2) + log n
Я не уверен, работает ли теорема здесь хозяин, и своего рода застрял ,
A
ответ
3
Это больше похоже на теорему Акра-Bazzi: http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method#The_formula с k=1, h=0, g(n)=log n, a=(2)^{1/2}, b=1/2. В этом случае p=1/2 и вам необходимо оценить значение \int_1^x log(u)/u^{3/2} du. Вы можете использовать интеграцию по частям или символический интегратор. Вольфрам Альфа рассказывает мне, что неопределенный интеграл равен -2(log u + 2)/u^{1/2} + C, поэтому определенный интеграл равен 4 - 2(log x + 2)/x^{1/2}. Добавляя 1 и умножая на x^{1/2}, получаем T(x) = \Theta(5x^{1/2} - 2 log x - 4).
1
Согласно основной теореме, ф (п) должна быть многочленом, но здесь
f(n) = logn
, который не является многочленом, поэтому он не может быть решена с помощью мастер-теоремы в соответствии с правилами. Я где-то читал о четвертом случае. Я должен также упомянуть об этом.
Он также обсуждается здесь: Master's theorem with f(n)=log n
Однако существует ограниченный «четвертый случай» для основной теоремы, которая позволяет ему обратиться к полилогарифмам.
Если
f(n) = O(nlogba logk n), then T(n) = O(nlogba log k+1 n).
Другими словами, предположим, что у вас есть Т (п) = 2Т (п/2) + п войти п. f (n) не является многочленом, но f (n) = n log n и k = 1. Поэтому T (n) = O (n log2 n)
См. этот раздаточный материал для получения дополнительной информации: http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-HandoutNoNotes.pdf
0
Master theorem имеют только ограничения на ваших a и b, которые хранятся для вашего случая. Тот факт, что a является иррациональным, и у вас есть log(n), так как ваш f(n) не имеет к этому отношения.
Так что в вашем случае ваш c = log2(sqrt(2)) = 1/2. Так как n^c растет быстрее, чем ваш журнал (n), сложность рекурсии равна O(sqrt(n)).
P.S. Решение Danyal ошибочно, поскольку сложность не является nlogn, и решение Эдварда Дулитта верно, также это излишний случай в этом простом случае.
Смежные вопросы
- 1. Т (п) = Т (п-1) + 10/п
- 2. решения рекурсии Т (п) = журнал (Т (п-1)) + 1
- 3. вычисления рекуррентное соотношение Т (п) = п + Т (п/2)
- 4. Решая мастер теорема с лог п: Т (п) = 2Т (п/4) + журнал п
- 5. временная сложность соотношения Т (п) = Т (п-1) + Т (п/2) + п
- 6. рекурсия Дерев и асимптотическая Сложность: Т (п) = Т (п/3) + Т (п/2) + п
- 7. Как решить эту рекуррентное соотношение: Т (п) = Т (п-1) * Т (п-2)
- 8. Решая время выполнения Т (п) = п^(1/2) Т (п^(1/2)) + п
- 9. Решая повторения Т (п) = Т (п/2) + Θ (1) заменой
- 10. Как решить: Т (п) = Т (п - 1) + п
- 11. сложность алгоритмов п * (т + п)^2
- 12. Рецидив: Т (п) = 3T (п/2) + п^2 (ЛГН)
- 13. Т (п) = Т (п/2) + Т (п/4) решить это повторение с помощью итерационного метода
- 14. Промежуточного этап рекуррентного соотношения Т (п) = 2T (п/2) + п/журнал (п)
- 15. асимптотической сложности Т (п) = Т (п-1) + 1/п
- 16. Как решить Т (п) = Т (п-2) + T (2) + п с рекурсии дерева
- 17. Рецидив отношений: Решение BIGO Т (п-1)
- 18. Применяя теорему магистра с F (п) = 2^п
- 19. Побег \ п \ т \ т в выходе JSon
- 20. Генерирование всех целых чисел п, п & т == п (т заданная целые числа) effeciently в C
- 21. Фибоначчи п по модулю т
- 22. Нахождение сложности Т (п) = 4T (п/2) + (N^2) * LOGN используя итерационный метод
- 23. как решить повторения Т (п) = Т (п-1) + T (N-3) -T (п-4), п> = 4
- 24. упрощают выражение к/т% п
- 25. Экспоненты в С (п^т)
- 26. Facebook, Twitter и т. П.
- 27. Получить временную сложность рекурсии: Т (п) = 4T (п-1) - 3T (п-2)
- 28. Как получить временную сложность этого рецидива: Т (п) = SQRT (п) * T (SQRT (п)) + п
- 29. Рецидив связь: Решение Big O Т (п-1)
- 30. Как распаковать кортеж длины п т <п переменных