Решение повторения T (n) = 2T (n/2) + n ^ 4

Я изучаю курс MIT и книгу CLRS Introduction to Algorithms.

В настоящее время я пытаюсь решить повторение (со страницы 107)

Т(n) = 2T(n/2) + n4

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

Уровень 0: n4

Уровень 1 2(n/2)4

Уровень 2 4(n/4)4

Уровень 3 8(n/8)4

Дерево имеет lg(n) уровней. Поэтому я думаю, что повторение должно быть

T(n) = Θ(n4 lg n)

Но, если я использую главную теорему, я получаю, что

Т(n) = Θ(n4)

Ясно, что оба они не могут быть правильными. Который правильный? И где я ошибся в своих рассуждениях?


recurrence algorithm math big-o big-theta
person huherto    schedule 05.01.2011    source источник

Ответы (4)


arrow_upward
6
arrow_downward

Второй выглядит правильно. Обратите внимание, что ваше дерево повторения выглядит как

n4 + 2(n/2)4 + 4(n/4)4 + ... + 2i< /sup> (n / 2i)4

Но 2(n/2)4 n4, потому что (n/2)4 = n4 / 16, поэтому 2(n/2)4 = n4/8. На самом деле, если вы поработаете над математикой, вы получите, что работа, выполняемая на уровне i, определяется выражением

n4 / (2-3i)

Таким образом, мы получаем (1 + 1/8 + 1/64 + 1/512 + ... ) n4, что, как можно показать, меньше 2n4. Итак, ваша функция (n4).

person templatetypedef    schedule 05.01.2011
comment
ах да, я вижу свою ошибку. Хорошее объяснение, почему оно меньше 2n^4. Спасибо - person huherto; 05.01.2011

arrow_upward
2
arrow_downward

С рекурсией это Θ (n ^ 4)

T(n) = 2*T(n/2) + n^4 
T(n) = 2( 2*T(n/4) + (n/2)^4) + n^4 = 4*T(n/4) + 2*(n/2)^4 + n^4
T(n) = 4(2*T(n/8) + (n/4)^4) + 2*(n/2)^4 + n^4 = 8*T(n/8) + 4*(n/4)^4 + 2(n/2)^4 + n^4

T(n) = 8*T(n/8) + n^4*(1 + 1/(2^3) + 1/(2^6))
...

T(n) = 2^k*T(n/(2^k)) + n^4*(1+ 1/(2^3) + 1/(2^6) + 1/(2^9)...+ 1/((2^(k-1))^3)

We know T(1) = 1

n = 2^k so k = log2(n) Then

T(n) = n*T(1) + n^4*( 1 - (1/(2^3))^k)/(1-1/8)

T(n) = n + (8/7)*n^4*(1 - n^(-3))

T(n) = n + (8/7)*(n^4 - n)

T(n) = (8/7)*n^4 - (1/7)*n


Θ(T(n)) = Θ((8/7)*n^4 - (1/7)*n)
Θ(T(n)) = Θ(n^4)

это Θ(n^4)

person Community    schedule 05.01.2011

arrow_upward
1
arrow_downward

Здесь вы можете напрямую использовать основную теорему.

Это уравнение соответствует случаю 1 основной теоремы, где log (a) base b < f( n)

a : количество повторений b : количество частей

log a base b = log 2 base 2 = 1 < n^4

Следовательно, по теореме Мастерса T(n) = theta(f(n)) = theta(n^4)

person CyprUS    schedule 07.10.2015

arrow_upward
0
arrow_downward

По основной теореме

a=2, b=2, f(n)=n^4

Первый шаг — вычислить n^(log a по основанию b) => n(log 2 по основанию 2) = n*1 = n Второй шаг — Is f(n)> Результат первого шага => n^4> n => ДА Это означает использование случая 3 основной теоремы.

Третий шаг - проверка условия регулярности

a. f(n/b) <= c. f(n) where c>1 
a(n/b) . log(n/b) <= c. f(n)
2.(n/2) . log(n/2) <= c. n^4
n.log(n/2) <= c.n^4

Да, условие Регулярности выполнено, значит, наше решение должно быть таким.

T(n) =theta (f(n)) = theta(n^4)
person Amit    schedule 31.01.2020