Как решить временную сложность T (n) = 9T (n/3) + 2n^2 + n/3 с использованием мастер-метода?

Question

Я не могу понять, что такое f (n)? Является ли n^2 или 2n^2 + n/3? Как решить такие вопросы? Заранее спасибо

Answer 1

ссылаясь на теорему мастер следующим образом: дано уравнение recusion

T(n) = b*T(n/c) + f(n), 

это справедливо для E = log(b)/log(c):

1. если f(n) в O(N^(E - eps)) для некоторого eps > 0, то T(n) в Theta(n^E);
2. если f(n) находится в Theta(N^E), то T(n) находится в Theta(N^E * log(n));
3. если f(n) в Omega(N^(E + eps)) для некоторого eps > 0 и дополнительно b*f(n/c) <= d*f(n) для некоторых d < 1 и n достаточно большой, то T(n) в Theta(f(n)).

В противном случае главная теорема вам не поможет. (Вы можете получить это определение из каждого базового учебника по алгоритмам или с помощью Google.)

Из вашего определения у нас есть b = 9 и c = 3 и f(n) = 2*n^2 + n/3. Поэтому нетрудно показать, что случай 2 имеет место как E = 2, а f(n) - в Theta(n^2). Поэтому T(n) находится в Theta(n^2 * log(n)).