Почему $ t (n)= 3t (n / 4) + n \ log n $ разрешит с Master Method, но $ t (n)= 2t (n / 2) + n \ log n $ нет?

Question

У меня есть трудности в понимании, почему рецидив

$$ t (n)= 3t (n / 4) + n \ log n $$

разрешит с помощью основного метода, но

$$ t (n)= 2t (n / 2) + n \ log n $$

не?

Несмотря на то, что они оба выглядят очень похожими, за исключением значений коэффициента коэффициента « $ a $ 'и размер резака" $ b $ '.

Я понимаю, что рабочая функция ' $ f (n) $ ' должна быть полиномиально больше / меньше, чем $ n^ {\ log_ba} $ .И что во втором рецидиве $ n ^ {\ log_22}= n $ не полиномиально сопоставим с $ f (n)=n \ log n $ .Таким образом, мастер-метод не может быть применен.Но почему его можно применять к первому рецидиву?

Я нашел эти примеры в CLRS Intro в книгу Algo, и не могу их понять.Можете ли вы объяснить.

Answer 1

Давайте будем использовать основную теорему, как указано на wikipedia . Рассмотреть рецидив $$ T (n)= at (n / b) + f (n). $$ Есть несколько случаев для рассмотрения:

1. Если $ f (n)= o (n ^ c) $ для $ c <\ log_b a $ < / span> затем $ t (n)=theta (n ^ {\ log_b a}) $ .
2. Если $ f (n)=theta (n ^ {\ log_b a} \ log kn kn) $ для $ k \ geq 0 $ затем $ t (n)=theta (n ^ {\ log_b a} \ log ^ {k + 1} n) $ < / span>.
3. Если $ f (n)=Omega (n ^ c) $ для $ c> \ log_b a $ и $ f (n) $ - это «разумный», то $ T (N)=Theta (F (n)) $ .

В третьем случае функция «разумная», если существует $ k <1 $ и $ n $ такое, что для $ n \ geq n $ , у нас есть $ af (n / b) \ leq kf (n) $ .

Есть также расширения второго случая, которые обрабатывают все значения $ K $ :

1. Если $ f (n)=theta (n ^ {\ log_b a} \ log kn kn) $ для $ k> - 1 $ затем $ t (n)=theta (n ^ {\ log_b a} \ log ^ {k + 1} n) $ < / span>.
2. Если $ f (n)=theta (n ^ {\ log_b a} \ log kn kn) $ для $ k= - 1 $ затем $ t (n)=theta (n ^ {\ log_b a} \ log \ log n) $ .
3. Если $ f (n)=theta (n ^ {\ log_b a} \ log kn kn) $ для $ k <- 1 $ затем $ t (n)=theta (n ^ {\ log_b a}) $ .

---

Теперь вернитесь к вашим рецидивам. Значения $ a, b $ и $ f (n) $ :

1. $ a= 3 $ , $ b= 4 $ , $ f (n)= n \ log n $ .
2. $ a= 2 $ , $ b= 2 $ , $ f (n)= n \ log n $ .

в первом рецидиве, $ f (n)=omega (n ^ 1) $ , где $ 1> \ log_4 3 $ , и, согласно третьему случаю главной теоремы, $ f (n)=theta (n \ log n) $ (Вы должны проверить, что функция $ n \ log n $ разумна).

во втором рецидиве, $ f (n)=theta (n ^ 1 \ log ^ 1 n) $ , где $ 1=log_2 2 $ , и, согласно второму случаю главной теоремы, $ f (n)=theta (n \ log ^ 2 n) $ .