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

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

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

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

Пусть g(n) = T(n)/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 + ...

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

Таким образом, T(n) = ng(n) = Тета(nвойти в систему.)

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

Answer 2

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

• ранг 0:

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

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

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

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

поскольку база журналов не имеет значения в тета-версии, мы получаем:

который:

что есть (в сигме):

который представляет собой гармонический ряд, равный:

и поскольку ln — это журнал с основанием е, а базы журналов не имеют значения в тэте, мы наконец получаем:

что равно:

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