Как решить рецидива.T (n).= T (N-1) + T (N / 2) + N?

Question

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

a) Количество уровней в дереве .

Поскольку левая сторона дерева уменьшается на 1 размером, поэтому он самый длинный путь от корня. Размер подблеме на уровне I - n-i. Настройка n - i= 1, когда оно попадает в размере 1, мы получаем количество уровней, i= n - 1.

b) Стоимость на узел в дереве : cn

C) Количество узлов на уровне I : это где я застрял. Не в состоянии найти узлы на уровне я, поскольку левая сторона уменьшается на 1, с правой стороны на половину. Естественно, дерево более плотно к левой стороне. Не каждый узел будет иметь два детей.

Если я могу получить ответ на C, я могу рассчитать t (n)= Стоимость уровня 0 + Стоимость уровня 1 + Стоимость уровня 2 + ... Стоимость уровня N-1. Если Y1 - количество узлов на уровне 1, y2 на уровне 2 и т. Д. ... Тогда
=> T (n)= cn + y1 * cn + y2 * cn + y3 * cn + .... yn-1 * cn, чтобы получить общую стоимость.

Может ли кто-нибудь едут мне на подход, который я принимаю? Это правильно? Могу ли я принять предположение, что для достаточно большого n, мы можем игнорировать t (n / 2), а затем продолжить? Отказ

Онлайн поиск путал меня. Проблема составляет 4,4-5 от CLR.

Пожалуйста, смотрите Здесь

Это решение говорит t (n)= o (2 ^ n) и t (n)= Omega (n ^ 2) и не объясняет, как.

Также см. Здесь

Это решение говорит t (n)= o (n ^ 2). Но противоречит вышеуказанному решению

Answer 1

Пусть $ s (n)= t (n) - 2n - 2 $ . Вы можете проверить, что $ S (N)= S (N-1) + S (N / 2) $ (игнорирование того факта, что $ n / 2 $ не должен быть целым числом). Это показывает, что добавка $ n $ термин не имеет большого значения.

Для большого $ n $ , у нас есть примерно $ S (N) - S (N-1) \ ок. S '(n) $ , и поэтому мы приводим к решению дифференциального уравнения $$ S '(N)= S (N / 2). $$ Рассмотрим $ f (n)=exp (\ tfrac {1} {2} \ log_2 ^ 2 n) $ . потом $$ f '(n)=exp (\ tfrac {1} {2} \ log_2 ^ 2 n) \ cdot \ frac {\ ln n} {(\ ln 4) n}, $$ тогда как $$ f (n / 2)=exp (\ tfrac {1} {2} (\ log_2 n - 1) ^ 2) \ около \ exp (\ tfrac {1} {2} \ log ^ 2 n) \ exp ( - \ log n)=exp (\ tfrac {1} {2} \ log ^ 2 n) \ cdot \ frac {1} {n}. $$ Это говорит о том, что по крайней мере, $ \ ln s (n)=theta (\ log ^ 2 n) $ .

Откуда это приходит? Вы можете подумать о $ s (n) $ (с соответствующим базовым случаем!) Как количество способов перейти от $ n $ до нуля, применяя две операции: вычесть 1 и разделите на 2. «Типичная» такая последовательность будет содержать примерно $ \ log_2n $ Многие операции второго типа, из-за $ \ Theta (n) $ Всего, что приводит к очень приблизительной оценке $ \ binom {\ theta (n)} {\ log_2 n} $ , который также имеет форму $ \ exp \ theta (\ log ^ 2 n) $ .

---

Рассматривать для конкретности следующее точное определение $ s (n) $ : базовый случай - $ s (0 )= 1 $ , а для $ n> 0 $ , $$ S (n)= s (n - 1) + s (\ lfloor n / 2 \ Rfloor). $$ Это последовательность a000123 . Knuth, почти линейный рецидив , показал, что $$ \ log_4 s (n) \ sim \ log_4 ^ 2 n, $$ То есть отношение двух терминов имеет тенденцию к 1 как $ n \ \ \ Infty $ . Вход OEIS содержит еще более точную асимптотику.

Answer 2

Я не согласен с гипнозом Фибоначчи, но я не в состоянии процентов уверен в моем ответе

Вы видите $ t (n)= t (n - 1) + c * n= o (n ^ 2) $

$ t (n)= t (n / 2) + c * n= o (n log n) $

Тем не менее, вы не получаете UR T (N), простым добавлением.

Если вы идете один уровень в рекурсии (вы можете нарисовать дерево)

T (N)= T (N-2) + T ((N-1) / 2) + T (N / 2-1) + T (N / 4) + [N + (N-1) + (N-1) / 2 + (N / 2-1) + N / 4]

Это, чтобы показать вам, это тоже не просто $ o (n ^ 2) $

Я должен выполнить его, но я подозреваю, что либо $ O (((n ^ 2) * log n) $ или же $ o ((n ^ 2) * n ^ {log n})= o (n ^ 3) $

{Есть термин n (1 + 1/2 + 1/4 + .. 1 / n), который распадается в шагах журнала n, я должен проверить снова}