Решение рекуррентности T (n) = 2T (n / 2) + n ^ 4

Question

Я учусь, используя MIT Courseware и книгу CLRS Введение в алгоритмы.

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

T (n) = 2T (n / 2) + n ⁴

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

Уровень 0: n ⁴

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

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

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

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

T (n) = & Theta; (n ⁴ lg n)

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

T (n) = & Theta; (n ⁴ )

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

Answer 1

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

n ⁴ + 2 (n / 2) ⁴ + 4 (n / 4) ⁴ + ... + 2 ⁱ (n / 2 ⁱ ) ⁴

Но 2 (н / 2) ⁴ & ne; n ⁴ , поскольку (n / 2) ⁴ = n ⁴ / 16 и т. д. 2 (n / 2) ⁴ = п ⁴ / 8. Фактически, если вы решите математику, вы получите, что работа, выполняемая на уровне i, определяется как

n ⁴ / (2 ^-3i )

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

Answer 2

с рекурсией это Θ (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)

Answer 3

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

Это уравнение подходит для случая 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)