Как рассчитать T (n) = 3T (n/3) + O (lg n)

Question

Я знаю, что означают O(lg n) и T(n), и в анализе алгоритма я не знаю, как рассчитать T(n) = 3T(n/3) + O(lg n). Должен ли я расширить его?

Так же, как:

T(n) = 3^2 *T(n/3^2) + O(lg n/3) + O(lg n) and so on... 

тогда я получаю

T(n) = 3^(log b^n) * T(1)+ 3^[log b^(n-1)]* lg (n/(3^[log b ^(n-1)])) ...+ O(lg n/3) +O(lg n) 

Но как я могу получить правильный ответ, и я могу получить легкий способ найти его?

Answer 1

Я думаю, вы можете использовать теорему Мастера.

T(n)=aT(n/b) + f(n) 
Here a=3, b=3 and f(n)=O(log n) 
f(n) = O(log n) = O(n) 

, который предполагает ответ как BigTheta(n)

магистратура теорема формулы плз см Википедию. Существует три правила и довольно простые.