Решение повторений

Я пытаюсь решить данную рекурсию, используя дерево рекурсии, T(n) = 3T(n/3) + n/lg n.

На первом уровне (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)).

На втором уровне оказывается n/(log(n/9)).

Могу ли я обобщить приведенное выше уравнение в виде n.loglogn

Это общее сомнение, которое у меня есть, мне нужно понять это.

Примечание. Любая функция, которая должна быть Theta(n^k log^k (n)) в этой функции k, должна >=1. И в этом случае k равно -1, поэтому главная теорема не имеет значения.

Chaitanya 10.02.2010 источник

comment

Вы ищете решение (в закрытой форме) или вычисляете сложность вычислений? - BlueRaja - Danny Pflughoeft 11.02.2010

Ответы (3)

arrow_upward
8
arrow_downward

Это правда, теорема Мастера не применяется.

T(n) = 3T(n/3) + n/logn.

Пусть g(n) = T(n)/n.

Тогда ng(n) = 3(n/3)*g(n/3) + n/logn.

Таким образом

g(n) = g(n/3) + 1/log n.

Это дает g(n) = Sum 1/log n + 1/log n/3 + 1/log n/9 +...

= Theta(Сумма 1/logn + 1/(logn -1) + 1/(log n - 2) + ...) = Theta(Интеграл 1/x между 1 и logn) = Theta(log log n).

Таким образом, T(n) = ng(n) = Theta(nlog logn.)

Вы правильно угадали.

Community 10.02.2010

comment

Похоже, есть ошибка прямо на шаге между вводом g(n)=T(n)/n и частью n*g(n)=...; n/logn никогда не поднималось до n^2/logn - Adam Miller; 12.09.2013

comment

Я немного слаб в исчислении, не могли бы вы объяснить мне, как вы получили от суммы 1/logn + 1/(logn-1) + 1/(logn-2) + ... к интегралу 1/x между 1 и логин. Я понимаю, что вы переписываете бесконечную предельную сумму как интеграл, но не понимаю, как это сделать. - Syed Souban; 14.08.2019

arrow_upward
5
arrow_downward

Если вы используете дерево для визуализации вопроса, вы увидите, что сумма каждого ранга равна:

ранг 0: