Trouver des relations de récurrence d'un algorithme

Question

Je lis mon livre de texte algorithmes, et je lis sur les relations de récurrence et de trouver les algorithmes grande O complexité. Je cours à travers cette ligne

"In the case of the merge-sort algorithm, we get the recurrence equation:

    t(n) = b                  if n < 2

         = 2t(n/2) +bn        if n >= 2

for b > 0

ma réponse était "comment diable ne nous savons que?!?!"

Je me demande donc s'il y a une approche systématique, ou tout simplement une façon logique d'obtenir ces relations de récurrence des algorithmes

quelqu'un peut expliquer d'où viennent les b et les deux 2 à partir?

Answer 1

L'algorithme de tri de fusion peut se résumer comme:

mergesort (array A) {
   mergesort (first half of A);
   mergesort (second half of A);
   merge the two halves and return;
}

Il y a un O (N) algorithme pour la fusion de deux tableaux de longueur N, à savoir sa complexité est bN pour une constante b > 0.

En supposant que la complexité de mergesort est T (N). Comme la moitié de N est N / 2, nous voyons que:

mergesort (array A) {                    T(N)    =
   mergesort (first half of A);          T(N/2)  +
   mergesort (second half of A);         T(N/2)  +
   merge the two halves and return;       bN
}

ce qui explique la N = 2 cas.

N <2 cas (cas de base où l'on arrête la récursion) est triviale.

Answer 2

Eh bien, cette déclaration est (probablement) la conclusion d'une discussion, ou tout au moins une déclaration, de l'algorithme en question. Sans les détails que je ne peux en suppositions éclairées, ce qui irait comme ceci:

• la première chose que l'algorithme n'est de vérifier si elle est appelée à traiter 0 ou 1 éléments. Si cela est vrai, il retourne immédiatement. Ainsi donc n < 2, il y a un coût fixe - appeler b
• Pour n >= 2, l'algorithme divise son entrée en deux morceaux, chacun d'une taille n/2, et lui-même appelle sur chaque morceau. Chacun de ces appel aura un coût de t(n/2), et il existe deux invocations
• Il y a donc un coût supplémentaire pour fusionner les deux morceaux ensemble - ce coût sera proportionnel à n - appelez b fois n

La seule petite bizarrerie est que ce n'est pas tout à fait évident pourquoi les deux facteurs constants qui se posent doivent être les mêmes -. Mais une partie du point d'analyse grand-O est que les facteurs de constants finalement importent peu

Answer 3

T(n) = c if n < d
     = A*T(n/b) + f(n)

où d> = 1 et il y a sous-problèmes et les sous-problèmes sont au maximum la taille n / b. f (n) est le temps supplémentaire total nécessaire pour diviser le problème en sous-problèmes et fusionner les solutions de sous-problème dans une solution à l'ensemble du problème.

est pour les algorithmes de diviser pour mieux régner.

Je me demande pourquoi il y a 2 à sous-problèmes tri fusion?