Используя метод мастеров

Question

На моем промежуточном этапе у меня возникла проблема:

T(n) = 8T(n/2) + n^3

, и я должен найти ее большую тета-нотацию, используя либо мастера, либо альтернативный метод.Так что я сделал

a = 8, b = 2 k = 3

log ₂ 8 = 3 = k

, следовательно, T (n) большая тета n ³ .Я получил 1/3 балла, поэтому я ошибаюсь.Что я сделал не так?

Answer 1

T (n) = aT (n / b) + f (n)

Вы применили версию, когда f (n) = O (n ^ (log_b (a) - e)) для некоторыхe> 0.

Это важно, вам нужно, чтобы это было верно для некоторого e> 0.

Для f (n) = n ^ 3, b = 2 и a = 8,

n ^ 3 = O (n ^ (3-e)) равно не верно для любого e> 0.

Таким образом, вы выбрали неверную версию МастераТеорема.

Вам необходимо применить другую версию теоремы Мастера:

, если f (n) = Theta ((log n) ^ k * n ^ log_b (a)) для некоторого k> = 0,

, затем

T (n) = Theta ((log n) ^ (k + 1) * n ^ log_b (a))

В вашемпроблема, вы можете применить этот случай, и это дает T (n) = Theta (n ^ 3 log n).

---

Альтернативный способ решения вашей проблемы будет:

T (n) = 8 T (n / 2) + n ^ 3.

Пусть g (n) = T (n) /n^3.

Тогда

n ^ 3 * g (n) = 8 * (n / 2) ^ 3 * g (n / 2) + n ^ 3

т.е. g (n) = g (n / 2) + 1.

Это означает, что g (n) = тета (logn) и, следовательно, T (n) = тета (n ^ 3 logn).