Perché $ t (n)= 3t (n / 4) + n \ log n $ solvibile con il metodo master ma $ t (n)= 2t (n / 2) + n \ log n $ non è?

Question

Sto avendo difficoltà a capire perché la recidiva

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

è risolvibile con il metodo principale ma

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

non è?

Nonostante sia molto simile, tranne i valori del coefficiente di coefficiente di coefficiente di coefficiente di coefficiente di coefficiente di coefficiente di coefficiente di coefficiente di coefficiente di coefficiente "> $ A $ A $ 'e taglia taglierina' $ B $ '.

Capisco che la funzione di lavoro " $ f (n) $ 'deve essere polinomia più grande / inferiore a $ n^ {\ log_ba} $ .E che in seconda ricorrenza $ n ^ {\ log_22}= n $ non è polinomia paragonabile a $ f (n)=n \ log n $ .Quindi il metodo principale non può essere applicato.Ma perché può essere applicato alla prima recidiva?

Ho trovato questi esempi in CLRS INTRO per il libro Ago, e non riesco a capirli.Puoi spiegare.

Answer 1

Usiamo il teorema master come indicato su wikipedia . Considera una recidiva $$ T (n)= at (n / b) + f (n). $$ Ci sono diversi casi da considerare:

.
1. se $ f (n)= o (n ^ c) $ per $ c <\ log_b a $ < / span> quindi $ t (n)=theta (n ^ {\ log_b a}) $ .
2. se $ f (n)=theta (n ^ {\ \ log_b a} \ log ^ kn) $ per $ k \ geq 0 $ quindi $ t (n)=theta (n ^ {\ \ log_b a} \ log ^ {k + 1} n) $ < / span>.
3. se $ f (n)=omega (n ^ c) $ per $ c> \ log_b a $ e $ f (n) $ è "ragionevole" allora $ t (n)=theta (f (n)) $ .

Nel terzo caso, una funzione è "ragionevole" se esistono $ k <1 $ e $ n $ tale che per $ n \ geq n $ , abbiamo $ AF (N / B) \ Leq KF (n) $ .

Ci sono anche estensioni del secondo caso che gestiscono tutti i valori di $ k $ :

.
1. se $ f (n)=theta (n ^ {\ \ log_b a} \ log ^ kn) $ per $ k> - 1 $ quindi $ t (n)=theta (n ^ {\ log_b a} \ log ^ {k + 1} n) $ < / span>.
2. se $ f (n)=theta (n ^ {\ \ log_b a} \ log ^ kn) $ per $ k= - 1 $ quindi $ t (n)=theta (n ^ {\ log_b a} \ log \ log n) $ .
3. se $ f (n)=theta (n ^ {\ \ log_b a} \ log ^ kn) $ per $ k <- 1 $ quindi $ t (n)=theta (n ^ {\ log_b a}) $ .

---

.

Ora torna alle tue recidive. I valori di $ A, B $ e $ f (n) $ sono:

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

nella prima ricorrenza, $ f (n)=omega (n ^ 1) $ , dove $ 1> \ log_4 3 $ , e così, in base al terzo caso del teorema master, $ f (n)=theta (n \ log n) $ (Devi verificare che la funzione $ n \ log n $ è ragionevole).

nella seconda ricorrenza, $ f (n)=theta (n ^ 1 \ log ^ 1 n) $ , dove $ 1=log_2 2 $ , e così, in base al secondo caso del teorema master, $ f (n)=theta (n \ log ^ 2 n) $ .