Сложность повторения

Question

Найдите жесткую асимптотику:

T (n) = 1, если n = 1

2T (n / 4) + T (n / 2) + n^2, если n> 1

Я попытался нарисовать дерево повторения. Первый ряд у меня был n², второй ряд у меня был (3/8) (n⁴), третий ряд у меня был (27/1024) (n⁸).. Не знаю, как продолжить оттуда. Заранее спасибо.

Answer 1

Я думаю, что основная теорема может быть применена в этой задаче. Это гораздо проще понять, чем дерево повторения.

Напишите формулу повторения в другой форме. добавлять T(n/2) как слева, так и справа.

T (n) + T (n / 2) = + 2T (n / 4) + 2T (n / 2) + n ²

T (n) + T (n / 2) = + 2 [T (n / 4) + T (n / 2)] + n ²

определять G(n) = T(n) + T(n/2), затем

G (1) = Θ (1)

G (n) = 2G (n / 2) + n ², если n > 1

Примените основную теорему к приведенной выше новой формуле повторения

G (n) = Θ (n ²)

то есть

T (n) + T (n / 2) = Θ (n ²)

для n > 1

T (n) = 2 * T (n / 4) + T (n / 2) + n ²

= T (n / 4) + [T (n / 2) + T (n / 4)] + n ²

= T (n / 4) + Θ (n2 / 4) + n2

= T (n / 4) + Θ (n2)

Примените основную теорему к приведенной выше новой формуле повторения

T (n) = Θ (n2)