Как решить это уравнение рекурсии T (n) = √2T (n/2) + log n, используя основную теорему?

Question

Я знаю, что это можно решить с помощью метода master, но как? пожалуйста помоги ?

Answer 1

я не уверен, если это правильно:

a = sqrt(2) 
b = 2 
f(n) = log n 
log(b) a = log (2) sqrt(2) = 1/2 

log n in O[n^(1/2)] 

поэтому среда нахождения логарифм числа п в О {п^(1/2)} (однако Мастер теорема не может применяется здесь)

решение в следующих потоков: Solving master theorem with log n: T(n) = 2T(n/4) + log n

в целом, мы видим, что ваш рецидивы O (n1/2) и Ω (n1/2) от верхнего и нижнего ограничивающего ваш повторяемость по более крупным и меньшим рецидивам. Поэтому, несмотря на то, что главная теорема здесь не применяется, вы все равно можете использовать Мастер-теорему, чтобы утверждать, что время выполнения будет Θ (n1/2).

Master's theorem with f(n)=log n

Обычно е (п) должна быть многочленом теорема мастера применять - он не применяется для всех функций. Однако для основной теоремы существует ограниченный «четвертый случай», что позволяет применять его к полилогарифмическим функциям.

https://en.wikipedia.org/wiki/Master_theorem

https://en.wikipedia.org/wiki/Big_O_notation

Answer 2

Ralf не является правильным, говоря вам, что вы не можете apply masters theorem.

Единственное ограничение состоит в том, что a >=1 и b >= 1, a, b может быть иррациональным, а f (n) может быть любым.

Log2(sqrt(2)) is 1/2, который помещает вас в первый случай, и ваше решение - O(n^0.5).