Définitions récursives, pile d'appels, recherche dichotomique, tri fusion, relations de récurrence et théorème maître.
Objectifs du chapitre
À la fin de ce chapitre, vous serez capable de:
écrire une définition récursive correcte, reconnaître son cas de base et son cas récursif, et justifier sa terminaison et sa correction par récurrence;
décrire ce qu'est la pile d'appels, ce que contient un cadre, pourquoi la profondeur de récursion est bornée et ce qu'est un débordement de pile;
compter les appels d'une récursion naïve, expliquer pourquoi Fibonacci récursif est catastrophique, et le corriger par mémoïsation ou par itération;
appliquer le schéma diviser pour régner à la recherche dichotomique et au tri fusion, et établir leur invariant, leur correction et leur coût;
poser et résoudre une relation de récurrence T(n)=aT(n/b)+f(n) par l'arbre de récursion, puis par le théorème maître, en sachant quelles hypothèses celui-ci exige;
démontrer qu'aucun tri par comparaisons ne peut descendre sous Θ(nlog2n), et situer le tri fusion par rapport à cette borne.
Définitions récursives
Un objet défini à partir de lui-même
Le chapitre 2 a décrit un algorithme comme une suite finie d'instructions non ambiguës, et a mesuré son coût en comptant les opérations élémentaires qu'il exécute. Tous les algorithmes rencontrés jusqu'ici — la recherche séquentielle, le tri par insertion, le tri par sélection — étaient itératifs: une boucle, un invariant, un compteur qui avance. Ce chapitre introduit la seconde manière de construire un algorithme, celle qui donne son nom à la moitié de l'informatique: la récursivité.
L'idée paraît d'abord circulaire. Pour définir une chose, on s'autorise à l'employer. Pour calculer une valeur, on s'autorise à appeler le calcul qu'on est en train de définir. Ce qui empêche la circularité de dégénérer en cercle vicieux est une discipline très simple, et c'est tout le contenu de la notion.
Retenez la forme: un cas de base, un cas récursif, et une taille qui décroît strictement. Une définition récursive à laquelle il manque l'un des trois est fausse, et elle est fausse de trois manières différentes. Sans cas de base, la descente est infinie. Sans cas récursif, la fonction n'est définie qu'en un point. Sans décroissance stricte — par exemple f(n)=f(n), ou f(n)=f(n+1)−1 — la définition ne détermine rien du tout, et le programme correspondant ne s'arrête jamais.
La factorielle
L'exemple canonique est la factorielle. La définition habituelle, n!=1×2×⋯×n, cache une récurrence: le produit des n premiers entiers est le produit des n−1 premiers, multiplié par n. On écrit donc
n!={1n⋅(n−1)!si n=0,si n≥1.(3.1)
Le cas de base est n=0 (avec la convention 0!=1, qui n'est pas un caprice: c'est le produit vide, et c'est le nombre de façons d'ordonner zéro objet, à savoir une). Le cas récursif fait décroître n de 1: partant de n, on atteint le cas de base après exactement n appels. La traduction en pseudocode est littérale.
fonction factorielle(n)
si n = 0 alors
retourner 1 # cas de base
sinon
retourner n * factorielle(n - 1) # cas récursif
et en Python, ligne pour ligne:
def factorielle(n): if n == 0: # cas de base return 1 return n * factorielle(n - 1) # cas récursif
La suite de Fibonacci
Le second exemple classique a deux cas de base et deux appels récursifs. La suite de Fibonacci est définie par
F0=0,F1=1,Fn=Fn−1+Fn−2(n≥2).(3.2)
Ses premiers termes sont 0,1,1,2,3,5,8,13,21,34,55,89,144,… Deux cas de base sont ici nécessaires, et non un seul: le cas récursif descend de deux crans, et sans F1 la chaîne partant de F3 passerait à côté de F0 sans jamais s'arrêter proprement. C'est une vérification à faire systématiquement: les cas de base couvrent-ils toutes les valeurs que le cas récursif peut atteindre par le bas?
Récursivité et récurrence: le même objet
Le lien entre un algorithme récursif et une démonstration par récurrence n'est pas une analogie: c'est une identité de structure. Une démonstration par récurrence d'une propriété P(n) comporte une initialisation — P(0) est vraie — et une hérédité — si P(n−1) est vraie alors P(n) l'est. Un algorithme récursif comporte un cas de base et un cas récursif. La correspondance est terme à terme, et elle fournit la méthode de preuve: pour prouver qu'un algorithme récursif est correct, on prouve son cas de base, puis on suppose l'appel récursif correct et on vérifie que le cas récursif en tire le bon résultat. Cette hypothèse est exactement l'hypothèse de récurrence.
Démonstration. Par récurrence sur n.
Terminaison. Le paramètre de l'appel décroît strictement d'une unité à chaque appel récursif et reste entier; la suite des paramètres n,n−1,… atteint donc 0 après exactement n appels, où le cas de base rend la main sans appeler quoi que ce soit. La chaîne d'appels est de longueur n+1, donc finie.
Initialisation. Pour n=0, le test est vrai et la fonction retourne 1=0!.
Hérédité. Soit n≥1 et supposons que factorielle(n - 1) retourne (n−1)!. L'appel factorielle(n) prend la branche récursive et retourne n⋅factorielle(n−1)=n⋅(n−1)!=n! par (3.1).
Par récurrence, la propriété vaut pour tout n≥0. □
Remarquez le confort de cette preuve: elle ne suit pas l'exécution. Elle ne descend pas la chaîne d'appels, elle ne tient pas de compte des multiplications en attente. Elle se contente de supposer que l'appel interne fait son travail. C'est le bénéfice principal de la récursivité — et, nous allons le voir, aussi son piège, car une preuve de correction ne dit rien du coût.
Question 3.1
Laquelle de ces définitions récursives est bien fondée, c'est-à-dire termine pour tout entier n≥0?
La pile d'appels
Ce qu'un appel coûte
Un appel de fonction n'est pas gratuit. Lorsqu'une fonction en appelle une autre, la machine doit se souvenir de l'endroit où elle en était: quelle instruction reprendre au retour, quelles valeurs les variables locales avaient. Cette information est rangée dans une zone de mémoire appelée la pile d'appels (call stack).
Ce fonctionnement «dernier entré, premier sorti» est celui d'une pile au sens des structures de données, que le chapitre 4 étudiera pour elle-même. Il suffit ici de retenir ce qu'il implique: les appels en attente occupent de la mémoire, et cette mémoire n'est libérée qu'au retour.
Suivons factorielle(4). L'appel initial empile un cadre où n=4; il ne peut pas rendre son résultat avant de connaître factorielle(3), dont le cadre s'empile par-dessus, et ainsi de suite. Quand n=0 est atteint, cinq cadres sont présents simultanément. Le cas de base retourne 1, son cadre est dépilé, le cadre n=1 calcule 1×1=1 et se dépile, puis 2×1=2, 3×2=6, 4×6=24. Les multiplications s'effectuent donc à la remontée, dans l'ordre inverse des appels. C'est exactement ce que la preuve du théorème 3.1 nous a dispensés de suivre.
La profondeur est bornée
La pile n'est pas extensible. Le système d'exploitation lui alloue une zone de taille fixée à la création du fil d'exécution, de l'ordre de quelques centaines de kibioctets à quelques mébioctets selon la plateforme; l'ordre de grandeur usuel pour le fil principal d'un programme est de 1 Mio à 8 Mio. Si un cadre occupe une centaine d'octets, cela autorise quelques dizaines de milliers à quelques centaines de milliers d'appels imbriqués — pas davantage.
Python place ce garde-fou très bas, précisément pour transformer un plantage en exception propre. Avec la limite par défaut de 1000, la profondeur maximale mesurée sur la machine utilisée pour ce chapitre est de 998 appels imbriqués; en la portant à 3000 avec sys.setrecursionlimit(3000), elle passe à 2998. La somme récursive d'une liste illustre la conséquence:
def somme(a, i=0): if i == len(a): # cas de base: plus rien à additionner return 0 return a[i] + somme(a, i + 1)
Cette fonction renvoie bien 404550 pour la liste des entiers de 0 à 899, et lève RecursionError: maximum recursion depth exceeded while calling a Python object sur une liste de 5000 éléments. Or additionner 5000 nombres n'est pas une prouesse: une boucle for le fait sans le moindre effort, et sans consommer un octet de pile supplémentaire. Voilà le premier avertissement du chapitre: une récursion dont la profondeur croît linéairement avec la taille de l'entrée est une bombe à retardement, alors qu'une récursion de profondeur logarithmique — celle du tri fusion, celle de la dichotomie — ne posera jamais de problème, car log2(106)≈20.
Question 3.2
Un tri fusion traite un tableau de n=1000000 éléments. Chaque niveau de récursion coupe le tableau en deux. Combien de cadres d'appel au maximum sont simultanément empilés, si l'on compte le cadre de l'appel initial? (Réponse: ⌈log2n⌉+1.)
Fibonacci récursif naïf: l'anatomie d'une catastrophe
Le programme
La traduction littérale de (3.2) tient en trois lignes et elle est correcte — la preuve est celle du théorème 3.1, avec deux cas de base et une récurrence forte.
def fib(n): if n <= 1: # cas de base: F(0) = 0, F(1) = 1 return n return fib(n - 1) + fib(n - 2)
Elle est aussi inutilisable. Sur la machine utilisée pour ce chapitre, fib(35) demande 1,976 seconde, alors que la même valeur F35=9227465 s'obtient par une boucle en 1,14 microseconde, soit un rapport de l'ordre de 1,7⋅106. Comprendre pourquoi est l'exercice le plus instructif du chapitre.
L'arbre des appels
Chaque appel fib(n) avec n≥2 en engendre deux, fib(n-1) et fib(n-2), qui en engendrent à leur tour. La structure de l'exécution est donc un arbre d'appels: la racine est l'appel initial, les enfants d'un nœud sont les appels qu'il déclenche, et les feuilles sont les appels qui retournent sans rien appeler, c'est-à-dire les cas de base.
Figure 3.1. Arbre des appels de la version récursive naïve de Fibonacci pour n = 5. Les quinze cercles sont les quinze appels effectivement exécutés. Les deux appels f(3), cerclés d'un trait plein, calculent exactement la même chose, chacun à partir de zéro; f(2), cerclé de tirets, est recalculé trois fois et f(1) cinq fois. Les huit feuilles f(1) et f(0) sont les seuls appels qui font un vrai travail, et ce travail consiste à retourner 0 ou 1.
La figure 3.1 rend la catastrophe visible. La branche de gauche descend jusqu'à f(1) en passant par f(4),f(3),f(2); mais f(3) apparaît une seconde fois comme fils droit de la racine, et son sous-arbre entier — cinq appels — est recalculé à l'identique. Rien dans le programme ne conserve la moindre valeur d'un appel à l'autre: chaque f(3) rencontré repart de la racine de son propre sous-arbre.
Combien d'appels, exactement
Le décompte n'a pas besoin d'être approché: il est exact et il se démontre par récurrence.
Démonstration. Par récurrence forte sur n.
Initialisation. Pour n=0 et n=1, l'appel prend le cas de base et n'en déclenche aucun autre: C(0)=C(1)=1. Or 2F1−1=2⋅1−1=1 et 2F2−1=2⋅1−1=1: la formule est vérifiée.
Hérédité. Soit n≥2 et supposons (3.3) vraie pour tous les indices strictement inférieurs à n. L'appel fib(n) compte pour un appel, puis déclenche fib(n-1) et fib(n-2); les deux sous-arbres sont disjoints, donc
en utilisant (3.2). Pour les feuilles: une feuille est un appel avec n≤1, un nœud interne en a exactement deux; dans un arbre binaire où tout nœud interne a deux enfants, le nombre de feuilles dépasse d'une unité le nombre de nœuds internes, donc feuilles =(C(n)+1)/2=Fn+1 et nœuds internes =Fn+1−1. □
Ces valeurs ont été vérifiées en instrumentant la fonction avec un compteur et en comparant, pour n de 0 à 12, le compteur à 2Fn+1−1: les deux coïncident à chaque ligne. Le tableau ci-dessous donne les valeurs mesurées.
n
5
10
20
30
35
40
Fn
5
55
6 765
832 040
9 227 465
102 334 155
Appels C(n)=2Fn+1−1
15
177
21 891
2 692 537
29 860 703
331 160 281
La croissance de Fn est exponentielle: on montre (et le chapitre 2 a donné l'outil, la comparaison asymptotique) que Fn∼φn/5 avec φ=(1+5)/2≈1,618, le nombre d'or. Par conséquent
C(n)=2Fn+1−1=Θ(φn),(3.4)
c'est-à-dire une complexité exponentielle. Chaque unité ajoutée à n multiplie le travail par 1,618; dix unités le multiplient par φ10≈123. Le tableau le confirme: de n=30 à n=40, le nombre d'appels passe de 2,7 millions à 331 millions, soit un facteur 123.
Mémoïsation: se souvenir
Le défaut est identifié — le même sous-problème est résolu de multiples fois — donc le remède aussi: se souvenir. On conserve dans un dictionnaire les valeurs déjà calculées et on les consulte avant de recalculer. C'est la mémoïsation (memoization, sans «r»: le mot vient du latin memorandum).
def fib_memo(n, memo=None): if memo is None: memo = {} if n in memo: # déjà calculé: on le relit return memo[n] if n <= 1: return n memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo) return memo[n]
Le changement est minime et l'effet massif. Chaque valeur Fk pour k de 0 à n n'est calculée qu'une fois; les appels supplémentaires se soldent par une lecture du dictionnaire. Le nombre d'appels devient linéaire en n et le coût aussi, au prix d'une mémoire Θ(n) pour le dictionnaire — un compromis temps-mémoire tout à fait typique.
Itération: ne rien empiler du tout
Mieux encore: la récurrence (3.2) ne fait intervenir que les deux valeurs précédentes. Il est donc inutile de mémoriser toute la suite. Deux variables suffisent.
def fib_iter(n): a, b = 0, 1 # invariant: a = F(k), b = F(k+1) for _ in range(n): # après k tours, a = F(k) a, b = b, a + b return a
L'invariant de boucle est écrit dans le commentaire, dans l'esprit du chapitre 2: avant le tour numéro k, on a a=Fk et b=Fk+1. Il est vrai au départ (a=F0=0, b=F1=1) et se conserve, puisque le nouveau couple est (Fk+1,Fk+Fk+1)=(Fk+1,Fk+2). Après n tours, a=Fn. Le coût est Θ(n) opérations et Θ(1) mémoire, et la pile ne grandit jamais.
Les trois coûts, mesurés
Les durées ci-dessous ont été mesurées avec time.perf_counter sous CPython 3.9.6, une exécution unique pour la version naïve et une moyenne sur mille exécutions pour les deux autres. Ce sont des mesures, pas des estimations; elles varient de quelques dizaines de pour cent d'une exécution à l'autre, et les ordres de grandeur seuls sont significatifs.
n
Appels (naïf)
Naïf
Mémoïsé
Itératif
10
177
0,014 ms
2,07 µs
0,41 µs
20
21 891
1,41 ms
4,44 µs
0,69 µs
30
2 692 537
175 ms
6,93 µs
0,98 µs
35
29 860 703
1 976 ms
8,14 µs
1,14 µs
Lisez ce tableau colonne par colonne. La colonne «naïf» est multipliée par 11 entre n=30 et n=35, ce qui est bien φ5≈11,1. Les colonnes «mémoïsé» et «itératif» croissent lentement et linéairement. À n=35, le rapport entre naïf et itératif atteint 1,7⋅106: la différence entre les deux programmes n'est pas une affaire de langage, de compilateur ou de machine, mais de classe de complexité, et aucun matériel n'y changera rien. En extrapolant la mesure par le facteur φ, la version naïve demanderait environ 22 secondes pour n=40, 45 minutes pour n=50, et près de 160 ans pour n=80 — alors que la version itérative répond en une microseconde.
Question 3.3
Classez ces quatre façons de calculer Fn pour n grand, de la plus coûteuse à la moins coûteuse, en départageant les deux méthodes linéaires par la mémoire qu'elles consomment.
Glissez les éléments pour les mettre dans le bon ordre
1.
Récursion naïve: Θ(φn) opérations
2.
Boucle à deux variables: Θ(n) opérations et Θ(1) mémoire
3.
Exponentiation rapide de la matrice de Fibonacci: Θ(log2n) multiplications
4.
Récursion mémoïsée: Θ(n) opérations et Θ(n) mémoire
La recherche dichotomique
Le problème et l'algorithme
Chercher une valeur dans un tableau trié est le premier exemple sérieux de diviser pour régner, et le plus simple: on divise, on résout une seule des deux moitiés, et il n'y a rien à recombiner.
L'idée est celle du jeu où l'on doit deviner un nombre entre 1 et 100: on propose 50, on apprend si la cible est au-dessus ou en dessous, et l'on a éliminé la moitié des possibilités en une question. Sur un tableau trié a[0..n−1], on compare la cible x à l'élément central a[m]; si a[m]=x c'est fini, si a[m]<x la cible ne peut être que dans la moitié droite, et si a[m]>x que dans la moitié gauche.
fonction dichotomie(a, x)
bas ← 0 ; haut ← longueur(a) - 1
tant que bas ≤ haut faire
m ← partie_entiere((bas + haut) / 2)
si a[m] = x alors retourner m
sinon si a[m] < x alors bas ← m + 1
sinon haut ← m - 1
retourner «absent»
Figure 3.2. Recherche dichotomique de la valeur 10 dans le tableau trié du cours. À chaque étape, le pivot est encadré en couleur et les cellules éliminées passent en traitillé gris. Trois sondages suffisent, et trois est aussi le pire cas pour sept éléments: la vérification exhaustive sur toutes les valeurs de 0 à 89, présentes ou absentes, n'a jamais dépassé trois étapes.
L'invariant et la correction
Démonstration.Invariant. Nous affirmons qu'au début de chaque tour de boucle, si x figure dans a, alors son indice appartient à l'intervalle [bas,haut].
Avant le premier tour, l'intervalle est [0,n−1] tout entier: l'invariant est vrai. Supposons-le vrai au début d'un tour. Trois cas. Si a[m]=x, on retourne m et la conclusion est acquise. Si a[m]<x, alors, le tableau étant trié, tout indice i≤m vérifie a[i]≤a[m]<x, donc aucun indice inférieur ou égal à m ne porte x; l'indice cherché, s'il existe, est donc dans [m+1,haut], qui est le nouvel intervalle. Le cas a[m]>x est symétrique. L'invariant est donc conservé.
Terminaison. Posons k=haut−bas+1, le nombre de candidats. Comme bas≤m≤haut, chacune des deux branches retire au moins l'élément m, donc k décroît strictement à chaque tour tout en restant entier positif ou nul. La boucle s'arrête donc, soit par un retour, soit quand k=0, c'est-à-dire bas>haut.
Correction. Si la boucle se termine par bas>haut, l'intervalle est vide; par l'invariant, x ne figure pas dans a, et retourner «absent» est correct.
Coût. Précisons la décroissance. Avec m=⌊(bas+haut)/2⌋, la moitié gauche compte m−bas=⌊(k−1)/2⌋ éléments et la moitié droite haut−m=⌈(k−1)/2⌉; dans les deux cas le nouveau nombre de candidats est au plus ⌊k/2⌋. Partant de k0=n, après t comparaisons il reste au plus ⌊n/2t⌋ candidats. La boucle s'arrête dès que ce nombre atteint 0, c'est-à-dire dès que 2t>n, soit t≥⌊log2n⌋+1. □
La formule (3.5) est d'une sobriété remarquable. Pour n=7 elle donne 3; pour n=106 elle donne 20; pour n=109 elle donne 30. Chercher dans un annuaire d'un milliard de noms coûte trente comparaisons. C'est ce que le chapitre 2 appelle Θ(log2n), et c'est la deuxième meilleure classe de complexité après Θ(1).
Question 3.4
Un tableau trié contient n=2000000 éléments. Combien de comparaisons la recherche dichotomique effectue-t-elle au pire?
Diviser pour régner
Le schéma général
La dichotomie est un cas particulier d'un schéma qui organise une grande partie de l'algorithmique.
Dans la dichotomie, a=1 (on ne résout qu'une moitié), b=2, et f(n)=Θ(1): une comparaison pour choisir la moitié, rien à combiner. Dans le tri fusion, a=2, b=2 et f(n)=Θ(n): la division est triviale (couper au milieu) mais la combinaison est le vrai travail.
Le tri fusion
Tout repose sur la fusion. Deux tableaux déjà triés se fusionnent en parcourant les deux de front avec un doigt sur chacun: on compare les deux éléments pointés, on recopie le plus petit, on avance le doigt correspondant, et l'on recommence. Quand un des deux est épuisé, on recopie le reste de l'autre.
fonction fusionner(G, D)
R ← tableau vide ; i ← 0 ; j ← 0
tant que i < longueur(G) et j < longueur(D) faire
si G[i] ≤ D[j] alors ajouter G[i] à R ; i ← i + 1
sinon ajouter D[j] à R ; j ← j + 1
ajouter le reste de G puis le reste de D à R
retourner R
Chaque tour de boucle effectue une comparaison et écrit un élément. Comme il y a ∣G∣+∣D∣ éléments à écrire au total et que la boucle s'arrête quand l'un des deux tableaux est épuisé, le nombre de comparaisons d'une fusion est compris entre min(∣G∣,∣D∣) et ∣G∣+∣D∣−1: la fusion de deux tableaux totalisant n éléments coûte Θ(n), ce qui est optimal puisqu'il faut de toute façon lire les n éléments.
La correction de la fusion tient dans un invariant: à chaque tour, R contient, triés, les i+j plus petits éléments de G∪D, et tous les éléments non encore recopiés leur sont supérieurs ou égaux. Il est vrai au départ (R vide) et se conserve, parce que le plus petit élément restant est nécessairement G[i] ou D[j] — les deux tableaux étant triés, aucun élément situé plus loin ne peut être plus petit que celui que son doigt pointe.
Démonstration. Par récurrence forte sur n. Si n≤1, le tableau est trié par définition et l'algorithme le retourne tel quel. Soit n≥2; supposons le résultat acquis pour toute taille strictement inférieure à n. Les deux moitiés ont pour tailles ⌊n/2⌋ et ⌈n/2⌉, toutes deux comprises entre 1 et n−1 dès que n≥2: l'hypothèse de récurrence s'applique et les deux appels retournent les moitiés triées. La fusion de deux tableaux triés retourne, par son invariant, un tableau trié contenant exactement leurs éléments. Le résultat est donc une permutation triée de a. La terminaison suit du même argument: la taille décroît strictement à chaque appel et le cas de base est atteint. □
Le tableau du cours, déroulé
Appliquons le tri fusion au tableau fixé du cours, [38,27,43,3,9,82,10] — celui-là même que le chapitre 2 trie par insertion. La figure 3.3 montre la descente, la remontée et le compte de comparaisons de chaque fusion; toutes ces valeurs proviennent de l'exécution effective de l'algorithme, pas d'un comptage à la main.
Figure 3.3. Tri fusion du tableau 38, 27, 43, 3, 9, 82, 10. Vers le bas, en gris, le découpage: chaque tableau est coupé en deux jusqu'aux sept singletons de la rangée centrale. Vers le haut, en couleur, la fusion, avec à droite de chaque boîte le nombre de comparaisons qu'a demandé cette fusion. Total: treize comparaisons, contre quinze pour le tri par insertion sur le même tableau.
Suivons la moitié droite, [3,9,82,10]. Elle se coupe en [3,9] et [82,10]. Chacune se coupe en deux singletons, déjà triés. Fusionner [3] et [9] demande une comparaison (3≤9) et donne [3,9]; fusionner [82] et [10] en demande une aussi (82>10) et donne [10,82]. Fusionner [3,9] et [10,82] demande deux comparaisons: 3≤10 recopie 3, 9≤10 recopie 9, et la moitié gauche est épuisée — le reste, [10,82], est recopié sans aucune comparaison. On obtient [3,9,10,82] pour quatre comparaisons au total sur cette branche.
La fusion finale, celle de [27,38,43] et [3,9,10,82], en demande six: 27 contre 3, contre 9, contre 10, puis 27 contre 82 (recopie 27), 38 contre 82 (recopie 38), 43 contre 82 (recopie 43); la moitié gauche est épuisée et 82 est recopié gratuitement. Le grand total est 1+1+2+2+1+6=13.
Question 3.5
Combien de comparaisons le tri fusion effectue-t-il au pire sur un tableau de n=8 éléments? On utilisera la formule du pire cas n⌈log2n⌉−2⌈log2n⌉+1.
Relations de récurrence
Poser la récurrence
Le coût d'un algorithme diviser pour régner ne se lit pas dans une boucle: il se lit dans une équation. Si T(n) désigne le nombre d'opérations élémentaires sur une entrée de taille n, la définition même du schéma donne
T(n)=aT(bn)+f(n),T(1)=Θ(1),(3.6)
avec a≥1 sous-problèmes de taille n/b (b>1) et un coût f(n) pour diviser et combiner. Pour le tri fusion, a=2, b=2 et f(n)=Θ(n) — la fusion coûte un passage sur les n éléments. Pour la dichotomie, a=1, b=2 et f(n)=Θ(1).
Nous écrivons n/b sans nous soucier de la divisibilité; en toute rigueur, il faudrait ⌊n/b⌋ et ⌈n/b⌉. On démontre que cela ne change pas l'ordre de grandeur de la solution, et nous l'admettons: la démonstration est un exercice de comptabilité sur les parties entières, sans idée nouvelle.
L'arbre de récursion
La méthode la plus éclairante pour résoudre (3.6) consiste à dessiner l'arbre des appels et à sommer le travail niveau par niveau. Au niveau k, il y a ak sous-problèmes, chacun de taille n/bk, chacun coûtant f(n/bk) hors appels récursifs. Le travail du niveau k vaut donc akf(n/bk). Les feuilles sont atteintes quand n/bk=1, soit k=logbn; il y a alors alogbn=nlogba feuilles, chacune de coût constant. D'où
Tout se joue alors dans la comparaison entre le coût des feuilles, nlogba, et le coût de la racine, f(n). Trois régimes apparaissent, et ce sont exactement les trois cas du théorème maître.
Premier régime: le travail par niveau croît vers le bas. Prenons le tri fusion, T(n)=2T(n/2)+n, avec n=8. Le niveau 0 compte un problème de taille 8, coût 8. Le niveau 1 compte deux problèmes de taille 4, coût 2×4=8. Le niveau 2: quatre problèmes de taille 2, coût 8. Le niveau 3: huit problèmes de taille 1, coût 8. Chaque niveau coûte n, et il y a log2n+1 niveaux, d'où T(n)=Θ(nlog2n). C'est le cas d'équilibre, celui où f(n)=n et nlog22=n coïncident.
Deuxième régime: les feuilles dominent. Prenons T(n)=4T(n/2)+n. Le niveau k coûte 4k⋅n/2k=2kn: il double à chaque descente. La somme est géométrique de raison 2 et vaut donc, à un facteur près, son dernier terme: 2log2nn=n2. Ici nlog24=n2 écrase f(n)=n, et T(n)=Θ(n2). La vérification numérique sur la récurrence exacte T(n)=4T(n/2)+n, T(1)=1, donne T(64)=8128 pour n2=4096, soit un rapport 1,98 qui tend vers 2: le Θ(n2) est bien la bonne réponse.
Troisième régime: la racine domine. Prenons T(n)=2T(n/2)+n2. Le niveau k coûte 2k(n/2k)2=n2/2k: il est divisé par deux à chaque descente. La somme géométrique de raison 1/2 converge et vaut au plus 2n2, d'où T(n)=Θ(n2) — le coût est celui du premier niveau seul. La vérification numérique donne T(128)=32640 pour n2=16384, soit un rapport 1,99 qui tend vers 2=∑k≥02−k.
Le théorème maître
Ces trois régimes se résument en un énoncé.
Ce théorème est admis. La raison est claire et vaut d'être dite: sa démonstration ne contient aucune idée que l'arbre de récursion ci-dessus n'ait déjà livrée, mais elle exige de traiter proprement les parties entières — les sous-problèmes n'ont pas tous exactement la taille n/bk — et de majorer la somme (3.7) par une série géométrique dans chacun des trois cas. C'est un travail technique de deux pages, mené dans le chapitre 4 de Cormen, Leiserson, Rivest et Stein. Ce qu'il faut retenir et savoir justifier, c'est l'argument de l'arbre: comparer le coût des feuilles au coût de la racine.
Trois applications
Explorateur 3.1 · Arbre d'appels: profondeur et facteur de branchement
À gauche, la version linéaire (un appel par niveau). À droite, l'arbre complet où chaque appel en engendre b. Modèle didactique: l'arbre binaire complet majore l'arbre de Fibonacci naïf, qui n'est pas complet.
Profondeur d3
Facteur de branchement b2
Feuilles bd
8
Appels de la récursion
15
Appels version linéaire
4
Profondeur de pile
4cadres
Rapport récursif / linéaire
3,8 ×
Lecture
b ≥ 2: coût exponentiel en d
Question 3.6
À quelle classe appartient la solution de T(n)=3T(n/2)+n?
La borne inférieure: aucun tri par comparaisons ne bat n log n
Nous savons trier en Θ(nlog2n). La question qui vient naturellement est: peut-on faire mieux? Une réponse négative à cette question n'est pas un aveu d'échec, c'est un théorème — et un théorème d'une nature particulière, car il ne parle pas d'un algorithme mais de tous les algorithmes d'une famille, y compris ceux que personne n'a encore écrits. C'est le sommet intellectuel de ce chapitre.
Le modèle: le tri par comparaisons
Il faut d'abord dire précisément de quoi l'on parle, car une borne inférieure n'a de sens que dans un modèle de calcul.
Le tri par insertion, le tri par sélection, le tri fusion, le tri rapide et le tri par tas sont des tris par comparaisons. Le tri par comptage et le tri par base n'en sont pas: ils utilisent les valeurs elles-mêmes comme indices, ce qui suppose un univers de valeurs restreint. Cette distinction est essentielle: le théorème ci-dessous ne s'applique pas à eux, et c'est pourquoi ils peuvent trier en Θ(n) dans leur domaine de validité.
L'arbre de décision
Fixons un algorithme de tri par comparaisons et une taille n, et supposons les n éléments deux à deux distincts. Exécutons l'algorithme. Son déroulement est entièrement déterminé par les réponses successives aux comparaisons qu'il pose: à entrée donnée, il pose une première comparaison, et selon la réponse — oui ou non — il pose une deuxième comparaison ou bien il conclut.
Deux observations, et le théorème est démontré.
La première: l'arbre a au moins n! feuilles. En effet, l'algorithme doit être correct sur chacune des n! façons d'ordonner n éléments distincts. Or deux entrées demandant des permutations différentes pour être triées ne peuvent aboutir à la même feuille: la feuille détermine la permutation appliquée, et une seule permutation trie une entrée donnée. Chacune des n! permutations doit donc étiqueter au moins une feuille.
La seconde: un arbre binaire de hauteur h a au plus 2h feuilles. Récurrence immédiate sur h: un arbre de hauteur 0 est une feuille, soit 1=20; un arbre de hauteur h a deux sous-arbres de hauteur au plus h−1, donc au plus 2⋅2h−1=2h feuilles.
Démonstration. Soit h la hauteur de l'arbre de décision de l'algorithme pour la taille n, c'est-à-dire son nombre de comparaisons dans le pire des cas. Les deux observations donnent
n!≤nombre de feuilles≤2h,
d'où 2h≥n! et, en passant au logarithme de base 2, h≥log2(n!). Comme h est entier, h≥⌈log2(n!)⌉, ce qui établit (3.8).
Minorons maintenant log2(n!) sans aucun outil sophistiqué. Dans le produit n!=1⋅2⋯n, ne conservons que les ⌈n/2⌉ derniers facteurs; chacun est supérieur ou égal à n/2. Donc
Pour n≥4 on a log2n−1≥21log2n, donc log2(n!)≥41nlog2n: la borne annoncée vaut avec α=1/4. □
La constante exacte, par Stirling
La minoration élémentaire ci-dessus suffit pour l'ordre de grandeur, mais elle est lâche d'un facteur 4. La formule de Stirling donne la valeur exacte de l'asymptotique:
avec log2e≈1,4427. Le terme dominant est donc bien nlog2n, et le second terme, −1,4427n, est linéaire: il ne change pas la classe de complexité. La qualité de l'approximation (3.9) a été vérifiée numériquement: pour n=100, log2(100!)=524,7650 et la formule de Stirling donne 524,7638, soit un écart relatif de 2,3⋅10−6; pour n=1000 l'écart relatif tombe à 10−7 environ.
Retenez la conclusion sous la forme la plus parlante: pour trier n objets, il faut au moins nlog2n−1,44n comparaisons, et le tri fusion en effectue au plus n⌈log2n⌉−2⌈log2n⌉+1, soit à peu près nlog2n−n. Le tri fusion est optimal à un facteur constant près, et même à un terme linéaire près. Il n'y a pas d'algorithme de tri par comparaisons dix fois plus rapide qui attendrait d'être découvert: la borne est une propriété du problème, pas une limite de notre ingéniosité.
Question 3.7
Quel est le nombre minimal de comparaisons, au pire des cas, que doit effectuer un tri par comparaisons sur n=10 éléments? On donnera ⌈log2(10!)⌉.
Les tours de Hanoï
Le problème
Trois piquets, n disques de diamètres tous différents empilés sur le premier par taille décroissante. Il s'agit de transporter la pile entière sur le troisième piquet en respectant deux règles: on ne déplace qu'un disque à la fois, et l'on ne pose jamais un disque sur un disque plus petit.
La solution récursive se lit presque sans y penser. Pour déplacer n disques de A vers C en s'aidant de B: déplacer les n−1 disques du dessus de A vers B (en s'aidant de C), déplacer le grand disque de A vers C, puis déplacer les n−1 disques de B vers C (en s'aidant de A).
procédure hanoi(n, depart, auxiliaire, arrivee)
si n = 0 alors retourner # rien à déplacer
hanoi(n - 1, depart, arrivee, auxiliaire)
déplacer un disque de depart vers arrivee
hanoi(n - 1, auxiliaire, depart, arrivee)
Quatre lignes. Il serait difficile de faire plus court, et une version itérative existe mais demande de raisonner sur la parité de n et sur un ordre cyclique des piquets — l'exemple parfait d'un problème où la récursivité est le bon outil, celui annoncé dans l'avertissement plus haut.
Notez que la correction se prouve exactement comme le théorème 3.1: si l'on admet que les deux appels récursifs déplacent correctement n−1 disques, alors la séquence complète est légale — pendant le déplacement du grand disque, les n−1 autres sont tous sur B, et le grand disque est plus grand que tous, donc aucune règle n'est violée.
Le nombre de coups
Démonstration.La formule. La structure de la procédure donne la récurrence
H(0)=0,H(n)=2H(n−1)+1(n≥1),(3.10)
puisqu'elle effectue deux fois le travail pour n−1 disques plus un déplacement. Montrons H(n)=2n−1 par récurrence. Pour n=0: 20−1=0. Si H(n−1)=2n−1−1, alors
H(n)=2(2n−1−1)+1=2n−2+1=2n−1.
L'optimalité. Soit M(n) le nombre minimal de déplacements, toutes stratégies confondues. Le plus grand disque doit quitter A au moins une fois. À l'instant où il quitte A pour aller sur C — ce doit être vers C, sinon il faudra l'en ressortir plus tard — les n−1 autres disques ne peuvent être ni sur A (ils seraient au-dessus de lui) ni sur C (ils empêcheraient de l'y poser): ils sont donc tous sur B. Les amener tous sur B coûte au moins M(n−1) déplacements; le grand disque en coûte au moins un; les ramener ensuite de B vers C en coûte au moins M(n−1). Donc M(n)≥2M(n−1)+1, avec M(0)=0; la même récurrence donne M(n)≥2n−1. Comme la procédure atteint cette valeur, M(n)=2n−1. □
Cette récurrence est du type T(n)=2T(n−1)+1: elle décrémente au lieu de diviser, et le théorème maître ne s'y applique pas, comme l'avertissement plus haut l'annonçait. Elle produit une complexité Θ(2n), exponentielle, et cette fois ce n'est pas une maladresse d'implémentation: c'est la difficulté intrinsèque du problème, puisque la borne inférieure vaut pour toute stratégie.
Synthèse
Une définition récursive comporte un cas de base, un cas récursif et une taille qui décroît strictement; les trois sont nécessaires. Prouver qu'un algorithme récursif est correct, c'est faire une démonstration par récurrence: le cas de base est l'initialisation, l'appel récursif est l'hypothèse de récurrence.
Chaque appel en cours occupe un cadre sur la pile d'appels (paramètres, variables locales, adresse de retour). La pile est de taille fixe: une récursion de profondeur linéaire finit par déborder — en Python, dès 998 appels avec la limite par défaut — alors qu'une récursion qui divise reste à une profondeur d'une vingtaine de cadres pour un million d'éléments.
La version récursive naïve de Fibonacci effectue exactement 2Fn+1−1 appels, soit Θ(φn) avec φ≈1,618: 15 appels pour n=5, 2 692 537 pour n=30, 331 160 281 pour n=40. La mémoïsation ramène le coût à Θ(n) temps et Θ(n) mémoire, la boucle à deux variables à Θ(n) temps et Θ(1) mémoire. Mesuré: 1,98 s contre 1,14 µs à n=35.
La recherche dichotomique dans un tableau trié coûte ⌊log2n⌋+1 comparaisons: 3 pour sept éléments, 20 pour un million, 30 pour un milliard. Son invariant est «si x figure dans le tableau, son indice est dans [bas,haut]».
Le schéma diviser pour régner (diviser, régner, combiner) conduit à T(n)=aT(n/b)+f(n), que l'arbre de récursion résout en comparant le coût des feuilles nlogba à celui de la racine f(n). Le en donne les trois cas; il est admis, ne couvre pas tous les , exige une condition de régularité au cas 3 et ne s'applique pas aux récurrences qui décrémentent.
Le tri fusion trie en Θ(nlog2n): 13 comparaisons sur le tableau du cours, contre 15 pour le tri par insertion et 21 pour le tri par sélection; 120 443 contre 25 078 356 à n=10000. Aucun tri par comparaisons ne peut descendre sous ⌈log2(n!)⌉≈nlog2n−1,44n comparaisons au pire — l'argument de l'arbre de décision — de sorte que le tri fusion est optimal à un terme linéaire près. Les , enfin, exigent déplacements, et pas un de moins.
Série d'exercices du chapitre 3Exercice 1 sur 5
Question 3.8
Combien d'appels la version récursive naïve de Fibonacci effectue-t-elle pour calculer F7=13? On compte l'appel initial.
Exercices
Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.
Exercice 3.1 · Trois définitions récursives
Pour chacune des fonctions suivantes, identifiez le ou les cas de base, le cas récursif, l'argument de décroissance, et dites si la définition est bien fondée. Si elle ne l'est pas, corrigez-la.
s(n) = somme des entiers de 1 à n: s(0)=0 et s(n)=n+s(n−1).
p(a,n)=an: p(a,0)=1 et p(a,n)=a⋅p(a,n−1). Proposez ensuite une version dont la profondeur soit logarithmique.
u(n): u(1)=1, u(n)=1+u(n/2) si n est pair, u(n)=1+u(3n+1) si est impair et .
Solution
1. Cas de base n=0, valeur 0; cas récursif s(n)=n+s(n−1); l'argument décroît de 1 et reste entier positif, donc le cas de base est atteint après n appels. La définition est bien fondée et l'on démontre s(n)=n(n+1)/2 par récurrence: c'est vrai pour , et . La profondeur de pile est , ce qui interdit en Python d'aller au-delà de quelques centaines: la boucle est ici strictement préférable.
Exercice 3.2 · Compter les appels et les additions
Soit fib la version récursive naïve.
Combien d'appels et combien d'additions fib(6) effectue-t-il?
Combien de fois fib(2) est-il évalué au cours de fib(6)?
Montrez que le nombre d'additions vaut Fn+1−1, et interprétez ce résultat.
Pour n=40, estimez le temps d'exécution de la version naïve sachant que la version mesurée traite n=35 en 1,98 s.
Solution
1. Par (3.3), C(6)=2F7−1=2×13−1=25 appels. Le comptage par exécution donne bien 25. Les additions se font aux nœuds internes, au nombre de F7−1=12.
Sur le tableau trié a=[3,9,10,27,38,43,82], déroulez la recherche de x=82 et celle de x=11, en donnant à chaque étape l'intervalle et le pivot.
Quelle est la valeur de x trouvée en une seule comparaison? Combien de valeurs du tableau demandent exactement trois comparaisons?
On modifie l'algorithme pour qu'il retourne, lorsque x est absent, l'indice où il faudrait l'insérer. Quel invariant faut-il alors maintenir, et que retourner à la sortie de boucle?
Justifiez que ⌊log2n⌋+1 est bien atteint, en exhibant une taille et une cible.
Solution
1. Recherche de 82 (exécutée):
Étape
bas
haut
m
a[m]
Décision
1
0
6
3
27
27<82: bas ←4
2
4
6
5
43
43<82: bas
Exercice 3.4 · Récurrences et théorème maître
Résolvez, en indiquant le cas du théorème maître utilisé ou en expliquant pourquoi il ne s'applique pas.
T(n)=4T(n/2)+n2.
T(n)=3T(n/4)+nlog2n.
T(n)=2T(n/2)+nlog2n.
T(n)=T(n−1)+n, avec T(1)=1 — la récurrence du tri par insertion au pire.
T(n)=2T(n/2)+Θ(1). Comparez au cas 2 de la dichotomie et commentez.
Solution
1.a=4, b=2, c=log24=2, nc=n2. Comme , c'est le : .
Exercice 3.5 · La borne n log n et ce qu'elle interdit
Un ami affirme avoir écrit un tri par comparaisons qui trie n éléments en Θ(n) comparaisons au pire. Démontrez qu'il se trompe.
Combien de comparaisons faut-il au minimum pour trier 5 éléments? Et 12?
On dispose de 12 pièces d'apparence identique dont une est fausse, plus lourde ou plus légère. On ne dispose que d'une balance à deux plateaux, qui indique «gauche plus lourd», «équilibre» ou «droite plus lourde». Donnez une borne inférieure sur le nombre de pesées nécessaires pour identifier la fausse pièce et dire si elle est plus lourde ou plus légère.
Le tri fusion effectue au plus n⌈log2n⌉−2⌈log2n⌉+1 comparaisons. Pour n=1000, comparez cette majoration à la borne ⌈log2(n!)⌉ et concluez.
Solution
1. Par le théorème 3.6, tout tri par comparaisons effectue au moins ⌈log2(n!)⌉≥41nlog2n comparaisons au pire. Si le tri de l'ami était en , il existerait une constante telle que son pire cas soit au plus pour assez grand. On aurait alors , soit pour tout assez grand — impossible, n'étant pas bornée. La seule échappatoire serait que son algorithme ne soit pas un tri par comparaisons: il faut alors lui demander quelle autre opération il utilise et sur quel univers de valeurs.
Références
Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C., Introduction to Algorithms, 4e édition, MIT Press — chapitres 2 (tri fusion, invariants), 4 (récurrences, théorème maître, Strassen) et 8 (borne des tris par comparaisons).
Sipser, M., Introduction to the Theory of Computation, Cengage — pour le lien entre récursivité, récurrence et définitions inductives.
Knuth, D. E., The Art of Computer Programming, volume 3: Sorting and Searching, Addison-Wesley — section 5.3.1 pour le nombre minimal de comparaisons et l'algorithme de tri par fusion-insertion.
Abelson, H., Ledeen, K. & Lewis, H., Blown to Bits, Addison-Wesley — pour la portée des ordres de grandeur exponentiels hors de l'informatique.
Polycopiés du cours ICC de l'EPFL, partie «algorithmique et complexité».
0
89
3
si f(n)=Θ(nc), alors T(n)=Θ(nclog2n);
s'il existe ε>0 tel que f(n)=Ω(nc+ε), et s'il existe une constante κ<1 telle que af(n/b)≤κf(n) pour tout n assez grand (condition de régularité), alors T(n)=Θ(f(n)).
diminuée
divisée
nc=n0=1
f(n)=Θ(1)=Θ(nc)
cas 2
Θ(n2)
T(n)=8T(n/2)+Θ(n2)
c=log28=3
f(n)=Θ(n2)=O(n3−1)
cas 1
T(n)=Θ(n3)
sept
Θ(n2)
n=4096
n3=6,87⋅1010
nlog27=1,38⋅1010
4,96
n
théorème maître
f
tours de Hanoï
2n−1
Problème guidé 3.1 · Le maximum d'un tableau, par dichotomie
On cherche le maximum d'un tableau a de n éléments (non trié) par diviser pour régner: si n=1, le maximum est l'unique élément; sinon on coupe le tableau en deux moitiés, on calcule le maximum de chacune par un appel récursif, et l'on retourne le plus grand des deux. On veut le nombre exact de comparaisons, sa classe de complexité, et la comparaison avec la boucle usuelle. On prendra n une puissance de deux pour éviter les parties entières.
1
Poser la récurrence
Notez C(n) le nombre de comparaisons effectuées pour un tableau de taille n. Le cas de base ne compare rien. Le cas récursif effectue deux appels sur des tableaux de taille n/2, puis une comparaison pour choisir entre les deux maximums.
Question
Quelle relation de récurrence vérifie C?
Résoudre par l'arbre de récursion
La forme générale, et le théorème maître
Comparer avec la boucle
n
n≥3
n=0
s(n)=n+(n−1)n/2=n(n+1)/2
n+1
2. Cas de base n=0, valeur 1; cas récursif p(a,n)=ap(a,n−1), décroissance de 1: bien fondée, n multiplications et profondeur n+1.
Version logarithmique, par exponentiation rapide: on utilise an=(an/2)2 si n est pair, et an=a⋅(a(n−1)/2)2 si n est impair.
fonction puissance(a, n)
si n = 0 alors retourner 1
r ← puissance(a, partie_entiere(n / 2))
si n est pair alors retourner r * r
sinon retourner a * r * r
L'argument est divisé par deux (à une unité près) à chaque appel: la profondeur est ⌊log2n⌋+1 et le nombre de multiplications est au plus 2⌊log2n⌋. Pour n=1000, cela fait au plus 18 multiplications au lieu de 1000. Remarquez le point essentiel: on n'appelle puissancequ'une fois et on réutilise r deux fois. Écrire puissance(a, n/2) * puissance(a, n/2) produirait un arbre binaire complet de 2log2n=n feuilles et ramènerait le coût à Θ(n) — c'est exactement l'erreur de Fibonacci naïf.
3. C'est la suite de Syracuse (ou de Collatz). Les deux cas récursifs ne décroissent pas tous les deux: 3n+1 est plus grand que n. On ne peut donc pas conclure à la bonne fondation par l'argument standard, et de fait personne ne sait si cette récursion termine pour tout n: la conjecture de Collatz, ouverte depuis 1937, affirme que oui. Elle a été vérifiée par ordinateur pour tous les entiers jusqu'à des ordres de grandeur de 1020, ce qui ne constitue pas une démonstration. On ne peut pas «corriger» cette définition sans changer le problème; on peut seulement borner la récursion par un compteur et signaler l'échec au-delà. C'est un excellent exemple à garder pour le chapitre 5: décider si un programme s'arrête est, en général, indécidable.
2. L'exécution instrumentée de fib(6) compte les appels par valeur d'argument: f(6) une fois, f(5) une fois, f(4) deux fois, f(3) trois fois, f(2)cinq fois, f(1) huit fois, f(0) cinq fois. Total: 1+1+2+3+5+8+5=25, cohérent avec la question 1. On reconnaît au passage les nombres de Fibonacci dans la colonne des multiplicités: le nombre d'évaluations de f(k) au cours de fib(n) vaut Fn−k+1 pour 1≤k≤n, ici F6−2+1=F5=5.
3. Chaque nœud interne de l'arbre d'appels effectue exactement une addition (celle de fib(n-1) + fib(n-2)) et les feuilles n'en font aucune. Dans un arbre binaire dont tout nœud interne a exactement deux enfants, feuilles = internes +1; comme le total est 2Fn+1−1, les feuilles sont au nombre de Fn+1 et les internes de Fn+1−1.
L'interprétation est frappante: pour obtenir Fn, la fonction additionne 1 à lui-même Fn+1−1 fois. Elle reconstruit le nombre unité par unité — au sens propre, puisque les feuilles rendent 0 ou 1 et que tout le reste est de l'addition. Un algorithme qui construit son résultat par incréments de taille 1 ne peut évidemment pas être meilleur que linéaire en la valeur du résultat, et Fn croît exponentiellement en n.
4.C(40)/C(35)=331160281/29860703=11,09, ce qui est bien φ5≈11,09. Le temps estimé est donc 1,98×11,09≈22 s. Pour n=50, multiplier encore par φ10≈123: environ 2700 s, soit trois quarts d'heure. Pour n=80: environ 160 ans. La version itérative répond en 1,2 µs dans les trois cas.
←6
3
6
6
6
82
trouvé à l'indice 6
Recherche de 11 (absent):
Étape
bas
haut
m
a[m]
Décision
1
0
6
3
27
27>11: haut ←2
2
0
2
1
9
9<11: bas ←2
3
2
2
2
10
10<11: bas ←3
À la sortie, bas =3> haut =2: l'intervalle est vide et l'algorithme répond «absent», en trois comparaisons.
2. Le pivot initial est m=3, donc x=27 est trouvé en une comparaison. En exécutant l'algorithme sur les sept valeurs: 27 demande 1 comparaison, 9 et 43 en demandent 2, et 3, 10, 38, 82 en demandent 3. Quatre valeurs demandent donc exactement trois comparaisons — ce sont les feuilles du dernier niveau de l'arbre de décision de la dichotomie.
3. L'invariant devient: tous les éléments d'indice strictement inférieur à bas sont <x, et tous ceux d'indice strictement supérieur à haut sont >x. Il est vrai initialement (les deux ensembles sont vides) et se conserve par les mêmes trois cas. À la sortie, bas = haut +1, donc tout ce qui précède bas est <x et tout ce qui suit haut, c'est-à-dire tout ce qui est à partir de bas, est >x: bas est exactement la position d'insertion. Sur l'exemple du 11 ci-dessus, on retourne 3, et insérer 11 à l'indice 3 donne bien [3,9,10,11,27,38,43,82].
4. Pour n=7, ⌊log27⌋+1=3, et l'on vient d'exhiber quatre cibles présentes plus une cible absente qui demandent trois comparaisons. Plus généralement, pour n=2k−1 l'arbre de décision est un arbre binaire parfait de hauteur k−1 et toutes les feuilles du dernier niveau demandent k=log2(n+1)=⌊log2n⌋+1 comparaisons. En exécutant l'algorithme sur toutes les cibles entières de 0 à 89, présentes ou non, le maximum d'étapes observé est 3 et il n'est jamais dépassé.
f(n)=n2=Θ(nc)
cas 2
T(n)=Θ(n2log2n)
2.a=3, b=4, c=log43=ln3/ln4≈0,7925. Ici f(n)=nlog2n, qui vaut Ω(nc+ε) avec par exemple ε=0,2 (puisque nlog2n≥n≥n0,9925 pour n assez grand). Condition de régularité: 3f(n/4)=3(n/4)log2(n/4)=43n(log2n−2)≤43f(n), avec κ=3/4<1. Cas 3: T(n)=Θ(nlog2n).
3.a=2, b=2, c=1, nc=n. Ici f(n)/nc=log2n, qui tend vers l'infini: ce n'est pas le cas 2. Mais log2n=O(nε) pour toutε>0, donc f n'est pas Ω(n1+ε) et le cas 3 ne s'applique pas non plus. Le théorème maître ne conclut pas. On revient à l'arbre: le niveau k compte 2k sous-problèmes de taille n/2k, chacun coûtant (n/2k)log2(n/2k), soit un coût de niveau n(log2n−k). En sommant sur k=0,…,log2n−1:
4. La taille est décrémentée, pas divisée: le théorème maître ne s'applique pas. On déroule: T(n)=n+(n−1)+⋯+2+T(1)=n(n+1)/2=Θ(n2). On retrouve le coût quadratique du tri par insertion au pire.
5.a=2, b=2, c=1; f(n)=Θ(1)=O(n1−0,5), donc cas 1: T(n)=Θ(n). La comparaison avec la dichotomie est instructive. Les deux récurrences ont le même b et le même f, et ne diffèrent que par a: 1 pour la dichotomie (on ne visite qu'une moitié), 2 ici (on visite les deux). Cela suffit à faire passer le coût de Θ(log2n) à Θ(n). Le gain de la dichotomie ne vient donc pas du découpage en deux, mais du fait qu'elle jette une moitié.
Θ(n)
K
Kn
n
41nlog2n≤Kn
log2n≤4K
n
log2n
2.5!=120 et 26=64<120≤128=27, donc ⌈log2120⌉=7: au moins 7 comparaisons, et cette borne est atteignable — on sait trier 5 éléments en 7 comparaisons. Pour n=12, 12!=479001600 et log2(12!)=28,84, donc au moins 29 comparaisons. Attention toutefois: pour n=12 cette borne n'est pas atteinte, le minimum vrai valant 30 (recherche exhaustive rapportée par Knuth). Une borne inférieure reste une borne inférieure.
3. Chaque pesée a trois issues, donc l'arbre de décision est ternaire et un arbre ternaire de hauteur h a au plus 3h feuilles. Le nombre de réponses possibles est 12×2=24 (quelle pièce, et dans quel sens). Il faut donc 3h≥24; comme 32=9<24≤27=33, il faut au moins 3 pesées. La borne est atteinte: une procédure en trois pesées existe, et le fait que 24≤27 de justesse explique pourquoi l'énigme est difficile — il ne reste presque aucune marge, donc chaque pesée doit séparer les cas aussi également que possible. Avec 13 pièces on aurait 26 réponses, encore possible en 3 pesées; avec 14 pièces, 28 réponses, c'est impossible.
4. Pour n=1000: ⌈log21000⌉=10, donc la majoration du tri fusion vaut 1000×10−210+1=10000−1024+1=8977. La borne inférieure vaut ⌈log2(1000!)⌉=⌈8529,40⌉=8530. Le rapport est 8977/8530=1,052: le tri fusion est à 5,2 % de l'optimum théorique absolu, tous algorithmes confondus, connus ou non. Sur une permutation aléatoire, la mesure donne d'ailleurs 8701 comparaisons en moyenne, soit 2,0 % au-dessus de la borne. Il n'y a donc, pour trier par comparaisons, aucune marge de progrès significative à espérer: la question est close, et c'est un théorème qui la clôt.