Решая рецидивы

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.

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

г (п) = г (п/3) + 1/п лог.

Это дает г (п) = SUM 1/журнал N + 1/журнал п/3 + 1/журнал п/9 + ...

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

Таким образом, Т (п) = п г (п) = Тета (п журнала LOGN.)

Вы предположили это право.

Answer 2

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

• Оценка 0:

(который равен до n/log (n)) - ранг 1:

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

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

(начиная с конца и идет в обратном направлении ..первый, когда я = журнал (Base3) п и затем вернуться)

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

который:

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

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

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

, который равен:

так, это theta (n log log n).