Pourquoi $ t (n)= 3t (n / 4) + n \ journal n $ solvable avec méthode maître mais $ T (n)= 2T (n / 2) + n \ journal n $ n'est pas?

Question

J'ai des difficultés à comprendre pourquoi la récurrence

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

est solvable avec la méthode principale mais

$$ t (n)= 2T (n / 2) + n \ journal n $$

n'est pas?

Malgré qu'ils ressemblent tous les deux très similaires, à l'exception des valeurs de coefficient ' $ A $ ' et de coupe de taille ' $ B $ '.

Je comprends que la fonction de travail ' $ f (n) $ ' doit être polynomiale plus grande / plus petite que $ N.^ {\ log_ba} $ .Et cela dans la deuxième récurrence $ n ^ {\ log_22}= n $ n'est pas comparable en polynomie à $ F (n)=n \ journal n $ .La méthode principale peut donc être appliquée.Mais pourquoi peut-il être appliqué à la première récurrence?

J'ai trouvé ces exemples dans CLRS Intro to Algo Livre et ne les comprends pas.Pouvez-vous s'il vous plaît expliquer?

Answer 1

Utilisons le théorème principal comme indiqué sur Wikipedia . Considérer une récurrence $$ T (n)= à (n / b) + f (n). $$ Il y a plusieurs cas à considérer:

1. Si $ f (n)= O (n ^ c) $ pour $ C <\ log_b a $ < / span> alors $ t (n)=theta (n ^ {\ log_b a}) $ .
.
2. si $ f (n)=theta (n ^ {\ log_b a} \ log ^ kn) $ pour $ K \ geq 0 $ alors $ t (n)=theta (n ^ {\ log_b a} \ log ^ {k + 1} n) $ < / span>.
3. si $ f (n)=oméga (n ^ c) $ pour $ C> \ log_b a $ et $ f (n) $ est "raisonnable" alors $ t (n)=theta (f (n)) $ .

Dans le troisième cas, une fonction est "raisonnable" s'il existe k <1 $ et $ n $ tel que pour $ n \ geq n $ , nous avons $ AF (n / b) \ Leq kf (n) $ .

Il existe également des extensions du deuxième cas qui gèrent toutes les valeurs de $ k $ :

1. si $ f (n)=theta (n ^ {\ log_b a} \ log ^ kn) $ pour $ K> - 1 $ alors $ t (n)=theta (n ^ {\ log_b a} \ journal ^ {k + 1} n) $ < / span>.
2. si $ f (n)=theta (n ^ {\ log_b a} \ log ^ kn) $ pour $ k= - 1 $ alors $ t (n)=theta (n ^ {\ log_b A} \ journal \ journal n) $ .
3. si $ f (n)=theta (n ^ {\ log_b a} \ log ^ kn) $ pour $ k <- 1 $ alors $ t (n)=theta (n ^ {\ log_b a}) $ .
. .

---

Retour à vos récidives. Les valeurs de $ a, b $ et $ f (n) $ sont:

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

dans la première récurrence, $ f (n)=oméga (n ^ 1) $ , où $ 1> \ log_4 3 $ , et ainsi, selon le troisième cas du théorème maître, $ f (n)=theta (n \ journal n) $ (Vous devez vérifier que la fonction $ n \ journal n $ est raisonnable).

dans la deuxième récurrence, $ f (n)=theta (n ^ 1 \ log ^ 1 n) $ , où 1 $=log_2 2 $ , et ainsi, selon le second cas du théorème principal, $ f (n)=theta (n \ log ^ 2 n) $ .