Решение рецидивов

Question

Пытаюсь решить данную рекурсию, используя дерево рекурсии, 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, поэтому основная теорема не входит в рисунок

Answer 1

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

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

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

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

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

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

Это дает g (n) = Сумма 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) = n g (n) = Theta (n log logn.)

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

Answer 2

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

• ранг 0:

(что равно n / log (n)) - ранг 1:

и так далее, с общей суммой n/log(n/(3^i)) для каждого ранга, где i - текущий ранг. итак, все вместе мы получаем:

если мы откроем уравнение, то получим:

(начиная с конца и возвращаясь назад .. сначала, когда i = log (base3) n, а затем возвращаясь)

так как база лога не имеет значения в тэте, мы получаем:

, что:

который (в сигме):

- гармонический ряд, равный:

и так как ln - это log с базой e, а базы тэгов не имеют значения в theta, мы наконец получаем:

, что равно:

Итак, это тета (n log log n).