Mergesort - nombre maximal d'appels récursifs

Question

Dans this SO answer il y avait un exemple avec le calcul du nombre d'appels récursion mergesort pour un tableau de longueur 32 (pire des cas): 1 + 2 + 4 + 8 + 16 + 32 = 63.

Il est assez trivial d'imaginer pourquoi c'est le cas - à chaque niveau de l'arbre nous avons des nœuds de puissance de 2 et nous passons toujours au niveau suivant jusqu'au dernier.

Je me demande comment calculer ce nombre (nombre maximum d'appels récursifs) pour un tableau de longueur arbitraire n? En pratique, le nombre semble être 2*n-1 mais je ne comprends pas pourquoi. Quelqu'un peut-il expliquer la logique derrière tout cela?

Answer 1

Voyons le motif. Si n = 1 il ya un seul appel (qui n'a rien à faire).

S'il est vrai pour n alors pour 2n notre premier appel divise en n et n, dont chacun nous trions dans 2n-1 appels, pour 4n-2 plus. Nous avons donc besoin de 1 + 4n-2 = 4n - 1 = 2*(2n)-1 et le résultat est valable.

S'il est vrai pour n et n+1 alors pour 2n+1 notre premier appel divise en n et n+1. Nous les classons avec d'autres appels 2n-1 et 2(n+1)-1 = 2n+1. Faire pour 1 + 2n-1 + 2n+1 = 4n + 1 = 2*(2n+1) - 1 appels. Donc, parce que c'est vrai pour 1, c'est vrai pour 2. Parce que c'est vrai pour 1 et 2, c'est vrai pour 3. Parce que c'est vrai pour 2, c'est vrai pour 4. Parce que c'est vrai pour 2. et 3 c'est vrai pour 5. Et ainsi de suite.

Vous pouvez facilement retourner cela et en faire une preuve formelle par forte induction.