Notion d'algorithme, pseudocode, terminaison et invariants, coût d'un algorithme, notations O, Oméga et Théta, tris élémentaires.
Objectifs du chapitre
À la fin de ce chapitre, vous serez capable de:
définir ce qu'est un algorithme et le distinguer d'une recette, d'une heuristique et d'un programme;
lire et écrire un algorithme dans le pseudocode du cours, et expliquer pourquoi ce cours n'utilise pas un langage de programmation pour cela;
démontrer la correction d'un algorithme itératif à l'aide d'un invariant de boucle, et sa terminaison à l'aide d'une quantité qui décroît strictement dans un ensemble bien fondé;
compter le coût d'un algorithme en opérations élémentaires, distinguer le meilleur cas, le pire cas et le cas moyen, et dire pourquoi on ne compte pas des secondes;
énoncer précisément les définitions de O, Ω et Θ avec leurs quantificateurs, et les utiliser sans leur faire dire ce qu'elles ne disent pas;
analyser le tri par sélection, le tri par insertion et la recherche séquentielle, et estimer la plus grande taille d'entrée traitable dans un temps donné.
Qu'est-ce qu'un algorithme?
Une définition de travail
Le mot vient du nom du mathématicien persan al-Khwārizmī (IXe siècle), dont le traité de calcul, traduit en latin, a donné à l'Occident la numération de position et les procédés de calcul écrit que vous utilisez encore pour poser une addition. Le mot désigne aujourd'hui l'objet central de l'informatique.
non ambiguës
Les quatre exigences sont indissociables:
finitude du texte: l'algorithme se décrit en un nombre fini d'instructions, même s'il traite une infinité d'entrées possibles;
non-ambiguïté: chaque instruction a un effet déterminé, indépendant de l'interprétation de qui l'exécute;
terminaison: pour toute entrée admissible, l'exécution s'arrête après un nombre fini d'étapes;
correction: la sortie est celle que la spécification du problème demande.
Il faut insister sur la troisième et la quatrième: elles ne vont pas de soi et elles se démontrent. Une suite d'instructions non ambiguës qui boucle indéfiniment sur certaines entrées n'est pas un algorithme pour ces entrées; une suite d'instructions qui s'arrête toujours mais renvoie parfois une mauvaise réponse n'est pas non plus un algorithme du problème posé. Le chapitre 5 montrera qu'il est en général impossible de décider mécaniquement si un texte donné s'arrête sur toutes ses entrées: la terminaison est une propriété qu'on prouve à la main, pas une propriété qu'une machine vérifie pour nous.
Un algorithme est indépendant de la machine qui l'exécute et du langage dans lequel on l'écrit. L'algorithme d'Euclide est le même que vous l'exécutiez avec un crayon, en Python sur un ordinateur portable ou avec des cailloux; ce qui change est le temps par étape, pas le nombre d'étapes.
Ce qu'un algorithme n'est pas
Une recette de cuisine. La comparaison est traditionnelle et instructive surtout par ses échecs. «Salez à votre goût», «faites revenir jusqu'à ce que ce soit doré», «ajoutez une pincée de sel» sont ambigus: deux cuisiniers obtiennent deux résultats. «Laissez reposer la pâte une heure» est non ambigu, mais la recette n'a ni entrée variable ni spécification de sortie vérifiable. Une recette est une procédure; il lui manque la précision et la spécification qui font l'algorithme.
Une heuristique. Une heuristique est une méthode qui donne souvent une bonne réponse, vite, sans garantie. «Pour aller d'une ville à l'autre, prenez toujours la route qui vous rapproche le plus de la destination» termine et est non ambiguë, mais elle peut vous mener dans une impasse: elle n'est pas correcte. Les heuristiques sont indispensables dans la pratique — la plupart des problèmes d'optimisation industriels sont traités ainsi — mais elles se jugent à leur qualité mesurée, pas à une démonstration de correction. Nous y reviendrons au chapitre 5 avec les problèmes NP-complets, pour lesquels on ne connaît pas d'algorithme exact rapide.
Un programme. Un programme est la réalisation d'un algorithme dans un langage de programmation, pour une machine donnée. Le même algorithme admet des milliers de programmes. Réciproquement, un programme contient beaucoup de choses qui ne relèvent pas de l'algorithme: la lecture d'un fichier, la gestion de la mémoire, le format d'affichage, les messages d'erreur.
Le plus vieil algorithme: Euclide
L'algorithme d'Euclide, décrit dans les Éléments (livre VII, vers 300 av. J.-C.), calcule le plus grand commun diviseur (greatest common divisor, gcd) de deux entiers. Il est probablement plus ancien qu'Euclide lui-même, et il est resté d'usage courant: c'est lui qui, au chapitre 9, permettra de calculer l'exposant privé du chiffrement RSA.
L'idée tient en une identité. Si a=qb+r avec 0≤r<b, alors tout diviseur commun de a et b divise r=a−qb, et tout diviseur commun de b et r divise a=qb+r: les deux paires ont exactement les mêmes diviseurs communs, donc le même pgcd:
gcd(a,b)=gcd(b,amodb),gcd(a,0)=a.(2.1)
On remplace donc le couple (a,b) par (b,amodb) jusqu'à ce que le second terme soit nul, et l'on lit le pgcd dans le premier.
Question 2.1
Laquelle de ces descriptions n'est PAS un algorithme au sens de la définition du cours?
Écrire un algorithme: le pseudocode
Les conventions de ce cours
Un algorithme doit être écrit quelque part. Nous utilisons un pseudocode en français, assez précis pour être non ambigu, assez souple pour ne pas se noyer dans la syntaxe d'un langage. Voici les conventions, fixées une fois pour toutes:
Pseudocode
Signification
x ← e
affecter à la variable x la valeur de l'expression e
pour i de 1 à n faire … fin pour
boucle bornée; i prend les valeurs 1, 2, …, n
tant que C faire … fin tant que
boucle conditionnelle; C est réévaluée à chaque tour
si C alors … sinon … fin si
alternative
retourner e
arrêter l'algorithme et produire e
A[i]
la i-ème case du tableau A, les indices allant de 1 à n
A.longueur
le nombre d'éléments de A
échanger A[i] et A[j]
permuter les deux cases
Les indices vont de 1 à n, comme en mathématiques. Attention: Python, comme la plupart des langages, numérote de 0 à n−1; les traductions ci-dessous en tiennent compte. L'algorithme d'Euclide s'écrit alors:
Euclide(a, b) // a ≥ 0, b ≥ 0, non tous deux nuls
tant que b ≠ 0 faire
r ← a mod b // reste de la division euclidienne
a ← b
b ← r
fin tant que
retourner a // a = pgcd(a₀, b₀)
et la version Python, qui fait exactement la même chose:
def euclide(a, b): """pgcd de a et b par divisions successives.""" while b != 0: a, b = b, a % b # affectation simultanée return a
Exécutée sur euclide(1071, 462), cette fonction renvoie 21, et math.gcd(1071, 462) renvoie également 21: les deux valeurs ont été obtenues en exécutant le code, non en le lisant.
Pourquoi du pseudocode plutôt qu'un langage
Trois raisons, dans cet ordre d'importance.
Séparer l'idée de sa réalisation. Le pseudocode ne dit rien du typage, de la gestion de la mémoire ou des bibliothèques disponibles. Ce qui reste est exactement ce dont on prouve la correction et dont on compte le coût. Quand nous écrirons «T(n)=n(n−1)/2 comparaisons», cette affirmation vaudra pour tout programme fidèle à l'algorithme, en Python, en C ou en tableur.
Éviter les faux amis. En Python, a, b = b, a % b est une affectation simultanée; en C, il faudrait une variable temporaire. En Python, liste1 + liste2 recopie les deux listes, ce qui coûte Θ(n) là où le lecteur croit lire une opération élémentaire. Le pseudocode n'a pas d'opération dont le coût soit caché: chaque ligne coûte ce qu'elle a l'air de coûter.
Rester lisible par un humain. Un algorithme est d'abord une idée qu'on communique. Les Éléments d'Euclide n'ont ni accolades ni point-virgules et se lisent encore vingt-trois siècles plus tard.
La correction: invariants et terminaison
Comment savoir qu'un algorithme fait bien ce qu'on lui demande? Tester ne suffit pas: un test montre la présence d'un défaut, jamais son absence. La correction se démontre, et la démonstration d'un algorithme itératif a toujours deux moitiés: un invariant pour la correction, un variant pour la terminaison.
L'invariant de boucle
C'est une récurrence déguisée: l'initialisation est le cas de base, la conservation est l'hérédité, et le troisième point est la lecture du résultat. L'art consiste à trouver le bon invariant — assez fort pour conclure, assez faible pour être conservé.
Prenons l'algorithme le plus simple qui soit, la somme des éléments d'un tableau:
Somme(A)
s ← 0
pour i de 1 à A.longueur faire
s ← s + A[i]
fin pour
retourner s
Démonstration. Prenons pour invariant la propriété
P(i):s=k=1∑i−1A[k]au deˊbut du tour d’indice i.
Initialisation. Avant le premier tour, i=1 et s=0; la somme vide ∑k=10A[k] vaut 0 par convention. Donc P(1) est vraie.
Conservation. Supposons P(i) vraie pour un i avec 1≤i≤n. Le corps de la boucle remplace s par s+A[i], c'est-à-dire par ∑k=1i−1A[k]+A[i]=∑k=1iA[k], puis le compteur passe à i+1. Au début du tour suivant, s=∑k=1(i+1)−1A[k]: c'est P(i+1).
Terminaison. La boucle s'arrête lorsque le compteur atteint n+1. L'invariant P(n+1) donne alors s=∑k=1nA[k], qui est bien la valeur retournée. □
La démonstration paraît lourde pour un résultat évident. C'est précisément l'intérêt de l'exercice: la même mécanique s'applique sans changement à des algorithmes dont le résultat n'a rien d'évident, et c'est elle qui fait apparaître les erreurs de bord — un pour i de 2 à n au lieu de 1 à n, un s ← A[i] au lieu de s ← s + A[i]. Un invariant qui ne se conserve pas signale exactement la ligne fautive.
La terminaison: un variant dans un ensemble bien fondé
Une boucle pour i de 1 à n termine par construction. Une boucle tant que ne termine pas par construction: il faut le prouver.
L'argument est immédiat: si la boucle effectuait une infinité de tours, les valeurs successives de V formeraient une suite infinie strictement décroissante dans E, ce que la bonne fondation interdit.
Les deux mots comptent. Strictement: une quantité qui décroît au sens large peut stagner indéfiniment. Bien fondé: une quantité réelle positive qui décroît strictement peut très bien ne jamais s'arrêter — la suite Vk=1/k décroît strictement dans R>0, qui n'est pas bien fondé, et la boucle correspondante tourne pour toujours. C'est pourquoi on choisit presque toujours un variant entier positif: le nombre d'éléments non encore traités, la valeur d'une variable, la différence entre une borne et un compteur.
Démonstration.Terminaison. Prenons pour variant V=b, la valeur courante de la seconde variable. Elle est entière et positive ou nulle tout au long de l'exécution, car un reste de division euclidienne l'est. À chaque tour, la nouvelle valeur de b est r=amodb, qui vérifie 0≤r<b par définition du reste: V décroît strictement à chaque tour, dans l'ensemble bien fondé N. La boucle s'arrête donc après un nombre fini de tours, et comme V part de b0 et diminue d'au moins 1 par tour, ce nombre est au plus b0.
Correction. Prenons pour invariant
I:gcd(a,b)=gcd(a0,b0)et(a,b)=(0,0).
Initialisation: au premier passage, (a,b)=(a0,b0) et I est trivialement vraie. Conservation: supposons I vraie et b=0. Le tour remplace (a,b) par (b,amodb), et l'identité (2.1) donne gcd(b,amodb)=gcd(a,b)=gcd(a0,b0); de plus la nouvelle première composante vaut b=0, donc le couple reste non nul. Terminaison: la boucle s'arrête avec b=0, donc avec a=0, et l'invariant donne gcd(a,0)=gcd(a0,b0). Or gcd(a,0)=a puisque tout entier divise 0. La valeur retournée est donc bien gcd(a0,b0). □
La borne «au plus b0 divisions» est correcte mais très mauvaise: sur (1071,462) elle annonce au plus 462 divisions, il y en a eu 3. L'exercice 2.1 de ce chapitre établit le vrai majorant — la première variable est divisée par deux au moins tous les deux tours, d'où au plus 2log2a0 divisions, soit un coût logarithmique en la valeur et donc linéaire en le nombre de chiffres — et son point 3 exhibe le pire cas, atteint sur deux termes consécutifs de la suite de Fibonacci. Noter la borne grossière d'abord, puis la raffiner, est une démarche normale: la terminaison et le coût sont deux questions distinctes.
Question 2.2
Remettez dans l'ordre les étapes d'une preuve de correction et de terminaison d'une boucle «tant que».
Glissez les éléments pour les mettre dans le bon ordre
1.
Exhiber un variant entier positif qui décroît strictement à chaque tour
2.
Conclure que la boucle s'arrête, faute de suite infinie décroissante dans N
3.
Vérifier qu'un tour de boucle préserve l'invariant (conservation)
4.
Vérifier que l'invariant est vrai avant le premier tour (initialisation)
5.
Combiner l'invariant et la négation de la condition de boucle pour lire le résultat
6.
Énoncer l'invariant, c'est-à-dire la propriété que la boucle préserve
Le coût d'un algorithme
Que compter, et pourquoi pas des secondes
La question naturelle — «combien de temps cela prend-il?» — est la mauvaise question, pour quatre raisons.
Une mesure en secondes dépend de la machine. Le même programme s'exécute dix fois plus vite sur un serveur récent que sur un téléphone d'il y a cinq ans. Le résultat mesuré parle du matériel autant que de l'algorithme.
Elle dépend de tout le reste. Langage, compilateur et ses options, système d'exploitation, autres processus, état des mémoires caches: deux exécutions consécutives du même programme sur la même machine ne donnent pas le même temps.
Elle n'est pas prédictive. On veut savoir ce qui se passera sur un million d'éléments après avoir mesuré sur mille. Une seconde mesurée ne s'extrapole pas; un nombre d'opérations, si.
Elle vieillit. Un chiffre de temps publié aujourd'hui sera faux dans trois ans. Un nombre d'opérations est une propriété mathématique de l'algorithme: il ne vieillit jamais.
On compte donc des opérations élémentaires: affectations, comparaisons, opérations arithmétiques, accès à une case de tableau — chacune supposée de coût constant, indépendant des valeurs manipulées. Ce modèle s'appelle la machine RAM (random access machine). Il est faux dans le détail (une multiplication coûte plus cher qu'une addition, un accès mémoire hors cache coûte cent fois un accès en cache) mais il est faux d'un facteur constant, et c'est exactement ce que l'analyse asymptotique accepte d'ignorer.
En pratique on ne compte même pas toutes les opérations: on choisit une opération dominante, celle dont le nombre est proportionnel au travail total. Pour un tri, c'est la comparaison entre deux éléments (parfois l'échange, quand déplacer coûte cher). Pour une recherche, c'est le test d'égalité. Pour Euclide, c'est la division. Compter l'opération dominante donne le bon ordre de grandeur et rend l'analyse faisable à la main.
La taille de l'entrée
Le choix n'est pas anodin. Tester si un entier N est premier en essayant tous les diviseurs jusqu'à N demande environ N divisions: c'est peu si l'on compte en fonction de N, mais l'entrée est l'écriture de N, longue de b=⌈log2(N+1)⌉ bits, et N=2b/2 est exponentiel en la taille de l'entrée. Un entier de 2048 bits, comme ceux du chapitre 9, mettrait cette méthode hors de portée pour toujours. Nous dirons toujours en quoi n se compte.
Meilleur cas, pire cas, cas moyen
Deux entrées de même taille ne coûtent pas forcément la même chose. Soit Dn l'ensemble des entrées de taille n et T(x) le nombre d'opérations dominantes effectuées sur l'entrée x.
Le pire cas est la mesure de référence, pour trois raisons: il donne une garantie valable sur toute entrée; il est souvent atteint par les entrées réelles (un fichier déjà trié, une liste presque triée); et il ne demande aucune hypothèse sur la provenance des données.
Le cas moyen est plus informatif quand il est calculable, mais il n'a de sens qu'avec sa loi. «Le tri par insertion fait en moyenne n2/4 comparaisons» est une phrase incomplète: incomplète de «lorsque l'entrée est une permutation tirée uniformément parmi les n! permutations de n éléments distincts». Si vos données arrivent presque triées — ce qui est fréquent —, cette moyenne ne décrit pas votre situation, et le tri par insertion se comporte bien mieux qu'elle ne le laisse croire.
Le meilleur cas ne sert presque jamais à juger un algorithme, mais il sert à en comprendre le comportement: un algorithme dont le meilleur cas est linéaire et le pire quadratique est un algorithme adaptatif, qui exploite la structure déjà présente dans l'entrée.
Question 2.3
Une recherche séquentielle parcourt un tableau de n=1000 éléments distincts jusqu'à trouver la valeur cherchée. Si cette valeur s'y trouve et que sa position est uniformément distribuée, combien de comparaisons sont faites en moyenne?
Les notations asymptotiques
Compter exactement les opérations est possible pour de petits algorithmes, pénible pour les autres, et surtout inutile: le résultat dépend de conventions arbitraires (compte-t-on l'incrémentation du compteur de boucle?) qui ne changent le total que d'un facteur constant. Ce qui importe est la loi de croissance du coût quand n grandit. Les trois notations qui suivent capturent exactement cela.
Grand O: une borne supérieure
Les deux quantificateurs sont l'essentiel de la définition. «Il existe c» autorise à ignorer tout facteur constant. «Il existe n0» autorise à ignorer tout comportement en petites tailles. Ce que O affirme, c'est une propriété de la queue du comportement, à une constante multiplicative près.
L'égalité de la notation f(n)=O(g(n)) est un abus d'écriture universellement toléré: O(g(n)) désigne en réalité un ensemble de fonctions, et il faudrait écrire f∈O(g). On ne peut donc pas retourner l'égalité: O(n)=n n'a aucun sens, et de f=O(n2) et h=O(n2) on ne conclut évidemment pas f=h.
Grand Oméga: une borne inférieure
Ω sert à énoncer des limites de principe: tout algorithme qui trie par comparaisons fait Ω(nlogn) comparaisons dans le pire cas (chapitre 3); tout algorithme qui lit son entrée fait Ω(n) opérations. Une borne inférieure ne parle pas d'un algorithme, mais du problème: elle dit qu'aucun algorithme, présent ou futur, ne peut faire mieux.
Grand Théta: l'ordre exact
Démonstration.(1) Si f=Θ(g), les constantes c2 et c1 de (2.4) fournissent immédiatement (2.2) et (2.3). Réciproquement, si f≤cg pour n≥n1 et f≥c′g pour n≥n2, alors les deux inégalités valent simultanément pour n≥max(n1,n2), avec c1=c′ et c2=c.
(2) Pour n≥1, chaque nk avec k≤d vérifie nk≤nd, donc
P(n)≤(k=0∑d∣ak∣)nd,
ce qui donne la majoration avec c2=∑k∣ak∣. Pour la minoration, posons S=∑k<d∣ak∣. Pour n≥1,
P(n)≥adnd−Snd−1=nd−1(adn−S)≥2adnd
dès que adn−S≥2adn, c'est-à-dire dès que n≥2S/ad. On prend donc c1=ad/2 et n0=max(1,⌈2S/ad⌉).
(3) Par définition de la limite avec ε=L/2, il existe n0 tel que L/2≤f(n)/g(n)≤3L/2 pour n≥n0, d'où (2.4) avec c1=L/2 et c2=3L/2. □
Le point 2 est la règle pratique: on ne garde que le terme de plus haut degré et on jette son coefficient. Le point 3 en donne la version «par les limites», souvent la plus rapide à appliquer.
Question 2.4
Parmi les affirmations suivantes, laquelle est FAUSSE?
Les classes de croissance
En pratique, le coût des algorithmes se range dans une poignée de classes. Les voici, avec le nombre d'opérations qu'elles demandent pour trois tailles, et la plus grande taille traitable en une seconde.
Classe
Nom
n=10
n=100
n=106
plus grand n en 1 s
Θ(1)
constant
1
1
1
toute taille
Θ(log2n)
logarithmique
3,3
6,6
19,9
2109
Θ(n)
linéaire
10
100
106
109
Θ(nlog2n)
quasi-linéaire
33
664
1,99⋅107
39 620 077
Θ(n2)
quadratique
100
104
1012
31 622
Θ(n3)
cubique
1 000
106
1018
1 000
Θ(2n)
exponentiel
1 024
1,27⋅1030
≈10301030
29
Θ(n!)
factoriel
3 628 800
9,33⋅10157
—
12
Toutes les valeurs de ce tableau ont été calculées en Python, avec des entiers exacts pour les puissances et les factorielles, et la dernière colonne par recherche dichotomique sur la fonction de coût elle-même. Quelques repères pour la lire:
La colonne de droite est la seule qui compte pour un ingénieur. Elle répond à «jusqu'où puis-je aller?». Un algorithme cubique traite mille éléments par seconde; un algorithme quadratique en traite trente et un mille; un algorithme quasi-linéaire en traite quarante millions.
Le passage de n2 à nlog2n change la nature du problème, pas seulement sa vitesse: on passe de dizaines de milliers d'éléments à des dizaines de millions, soit un facteur 1 253.
Deux classes sont hors jeu. À 109 opérations par seconde, un algorithme en Θ(2n) traite n=29 en une seconde et n=60 en 36,5 ans; un algorithme en Θ(n!) traite n=12. Gagner un facteur mille sur la machine fait passer 29 à 39 et 12 à 14: aucune machine ne sauvera un algorithme exponentiel. C'est pourquoi le chapitre 5 parlera de problèmes «intraitables» et non de problèmes «lents».
Le logarithme est presque gratuit. Traiter n en log2n opérations autoriserait n jusqu'à 2109, un nombre dont l'écriture décimale compte plus de trois cents millions de chiffres. Un algorithme logarithmique n'a, en pratique, pas de limite de taille — c'est le sens de la recherche dichotomique du chapitre 3.
Figure 2.1. Les quatre classes n, n log₂ n, n² et 2ⁿ. Les DEUX axes sont logarithmiques: en abscisse la taille n de 1 à un milliard, en ordonnée le nombre d'opérations de 1 à 10 puissance 18. Sur un tel graphique une puissance de n devient une droite, dont la pente est l'exposant, tandis que 2 puissance n devient une exponentielle: c'est le mur presque vertical de gauche. La ligne tiretée marque une seconde à 10 puissance 9 opérations par seconde, et chaque point plein indique où la courbe correspondante la franchit; la légende donne la valeur de n en ce point.
La figure 2.1 rend visible ce que le tableau énumère. Sur une double échelle logarithmique, n, nlog2n, n2 et n3 sont des droites (ou presque, pour la deuxième) de pentes croissantes: elles diffèrent d'un facteur, pas d'une nature. La courbe 2n, elle, n'est pas une droite: elle traverse les dix-huit décades de l'axe vertical alors que n n'a pas atteint 60. La distance entre les points de franchissement — 29, puis 31 622, puis presque quarante millions, puis un milliard — est la mesure honnête de ce qui sépare ces classes.
Explorateur 2.1 · Explorateur de coût: combien d'opérations, combien de temps?
Modèle déclaré: la machine exécute 10⁹ opérations élémentaires par seconde (hypothèse, de l'ordre de grandeur d'un cœur de processeur actuel) et un algorithme de classe f effectue exactement f(n) opérations. Faites glisser n — en échelle logarithmique — et changez de classe: la dernière lecture, la plus grande taille traitable en une seconde, ne dépend que de la classe et ne bouge pas quand n bouge.
Taille de l'entrée n (échelle log)1 000
Classe de complexitén²
Nombre d'opérations
1 000 000
Temps estimé à 10⁹ op./s
1,0 ms
Ordre de grandeur
instantané
Plus grand n en 1 seconde
31 622
Question 2.5
À raison de 109 opérations élémentaires par seconde, quelle est la plus grande taille n qu'un algorithme en n3 peut traiter en une seconde?
Question 2.6
Ordonnez ces classes de complexité de la plus coûteuse à la plus économique lorsque n devient grand.
Glissez les éléments pour les mettre dans le bon ordre
1.
n!
2.
2n
3.
nlog2n
4.
n2
5.
n3
6.
n
7.
log2n
8.
1
Deux tris élémentaires
Trier est l'exemple canonique, pour trois raisons: le problème est facile à énoncer, les algorithmes se comptent à la main, et les écarts entre eux sont spectaculaires. Nous prenons le tableau du cours, celui que le chapitre 3 reprendra pour le tri fusion:
A=[38,27,43,3,9,82,10],n=7,
dont le résultat trié est [3,9,10,27,38,43,82]. Tous les comptages qui suivent ont été obtenus en exécutant les deux algorithmes en Python avec un compteur, jamais en les lisant.
Le tri par sélection
L'idée: chercher le plus petit élément, le mettre en première position, recommencer sur le reste.
TriSelection(A)
n ← A.longueur
pour i de 1 à n − 1 faire
m ← i // indice du minimum du suffixe
pour j de i + 1 à n faire
si A[j] < A[m] alors m ← j fin si
fin pour
si m ≠ i alors échanger A[i] et A[m] fin si
fin pour
L'invariant de la boucle externe est: au début du tour i, les cases A[1..i−1] contiennent les i−1 plus petits éléments du tableau initial, rangés en ordre croissant, et elles ne bougeront plus. Il est vrai avant le premier tour (préfixe vide), conservé par la recherche du minimum du suffixe, et donne à la sortie (i=n) un tableau trié: la dernière case contient le maximum, faute de concurrent.
Sur le tableau du cours, l'exécution donne:
tour
tableau après le tour
échange
départ
38, 27, 43, 3, 9, 82, 10
—
i=1
3, 27, 43, 38, 9, 82, 10
oui
i=2
3, 9, 43, 38, 27, 82, 10
oui
i=3
3, 9, 10, 38, 27, 82, 43
oui
i=4
3, 9, 10, 27, 38, 82, 43
oui
i=5
3, 9, 10, 27, 38, 82, 43
non
i=6
3, 9, 10, 27, 38, 43, 82
oui
Comptage réel (Python): 21 comparaisons, 5 échanges. Les 21 comparaisons se lisent directement sur l'algorithme: le tour i en fait n−i, donc
T(n)=i=1∑n−1(n−i)=k=1∑n−1k=2n(n−1),(2.5)
soit 7⋅6/2=21 pour n=7. Ce nombre ne dépend pas du contenu du tableau: les deux boucles sont bornées, aucune n'a de sortie anticipée. Vérifié en Python: sur le tableau déjà trié comme sur le tableau trié à l'envers, le compteur affiche 21.
Tmin(n)=Tmoy(n)=Tmax(n)=2n(n−1)=Θ(n2).
C'est un algorithme non adaptatif: lui donner un tableau déjà trié ne lui fait rien gagner. Son seul atout est le nombre d'échanges, au plus n−1 (5 ici, et l'énumération exhaustive des 5040 permutations de sept éléments distincts donne un minimum de 0 et un maximum de 6). Quand déplacer un élément coûte très cher — de gros enregistrements sur disque — cet atout compte.
Le tri par insertion
L'idée est celle du joueur de cartes: on prend les éléments un par un et on insère chacun à sa place dans la partie déjà triée, en décalant ce qui doit l'être.
TriInsertion(A)
pour i de 2 à A.longueur faire
x ← A[i] // l'élément à insérer
j ← i − 1
tant que j ≥ 1 et A[j] > x faire // on compare, puis on décale
A[j + 1] ← A[j]
j ← j − 1
fin tant que
A[j + 1] ← x
fin pour
L'invariant de la boucle externe: au début du tour i, le sous-tableau A[1..i−1] contient les i−1 premiers éléments du tableau initial, triés. La boucle interne termine parce que j décroît strictement dans {0,1,…,i−1}, ensemble fini donc bien fondé. À la sortie, i=n+1 et A[1..n] est trié — remarquez qu'ici, contrairement au tri par sélection, les éléments du préfixe ne sont pas les plus petits du tableau, mais bien les premiers arrivés.
Figure 2.2. Le tri par insertion sur le tableau du cours, une ligne par étape. Le trait sous les cases marque le préfixe déjà trié, qui gagne une case à chaque étape; la case encadrée en couleur, au nombre en gras, est l'élément qui vient d'être inséré, à la position qu'il occupe après le décalage. La colonne de droite donne le nombre de comparaisons de l'étape — 1, 1, 3, 4, 1, 5 — et leur total, 15. Ces lignes sont produites par l'exécution de l'algorithme dans la figure elle-même, pas recopiées.
Deux étapes méritent d'être suivies à la main. À l'étape 3, on insère 3: il est plus petit que 43, que 38 et que 27, on le décale donc jusqu'en tête — 3 comparaisons et 3 décalages. À l'étape 5, on insère 82: une seule comparaison avec 43 suffit à constater qu'il est déjà bien placé — 1 comparaison, aucun décalage. C'est là toute la différence avec le tri par sélection: le tri par insertion s'arrête dès qu'il peut.
Démonstration. L'étape i (insertion de A[i] dans le préfixe trié de longueur i−1) fait au moins une comparaison — celle qui teste A[i−1] > x — et au plus i−1, lorsque x va en tête et que la boucle s'arrête faute de cases, sans comparaison finale. Sommer les bornes sur i=2,…,n donne n−1 et ∑i=2n(i−1)=n(n−1)/2. Les deux bornes sont atteintes: la première par un tableau croissant, la seconde par un tableau décroissant.
Pour le cas moyen, notons p∈{1,…,i} la position finale de x dans le préfixe de longueur i. Sous la loi uniforme sur les permutations, p est uniforme sur ces i positions. Si p≥2, l'algorithme effectue i−p décalages puis une comparaison qui échoue, soit i−p+1 comparaisons; si p=1, il décale i−1 fois et sort parce que j atteint 0, soit i−1 comparaisons. L'espérance de l'étape i vaut donc i1[(i−1)+∑p=2i(i−p+1)], ce qui est l'expression (2.6). Le terme dominant est i1⋅2i2=2i, dont la somme sur i≤n vaut ≈n2/4: le cas moyen est bien quadratique, environ la moitié du pire cas. □
La formule (2.6) a été confrontée à l'énumération exhaustive en Python: Tmoy(7)=2087/140=14,9071 et Tmoy(8)=5399/280=19,2821, reproduits exactement par les 5040 et 40320 permutations.
Figure 2.3. Nombre de comparaisons du tri par insertion en fonction de n, dans le meilleur cas (n moins 1, en brun), en moyenne (en tirets) et dans le pire cas (n fois n moins 1 sur deux, la courbe du haut). Les trois courbes sont calculées, la moyenne par la formule exacte du théorème 2.4, vérifiée par énumération exhaustive jusqu'à n = 8. Le cercle marque le tableau du cours: 15 comparaisons pour n = 7, à un dixième de comparaison de la moyenne. La courbe moyenne est asymptotiquement la moitié de la pire, ce qui ne change pas la classe.
La figure 2.3 illustre un point que l'analyse asymptotique masque et que l'ingénieur doit voir: la moyenne et le pire cas sont dans la même classe. Passer de n2/2 à n2/4 divise le temps par deux, ce qui est appréciable mais ne change ni la courbe ni la taille maximale traitable d'un facteur significatif (2≈1,41). La seule chose qui change vraiment la classe est le meilleur cas, linéaire: c'est ce qui rend le tri par insertion excellent sur des données presque triées, et c'est pourquoi les bibliothèques standard l'utilisent encore — à l'intérieur d'algorithmes plus rapides, sur les petits sous-tableaux.
Question 2.7
Sur un tableau de n éléments DÉJÀ TRIÉ, combien de comparaisons font respectivement le tri par sélection et le tri par insertion?
La recherche séquentielle
Après trier, chercher. Le problème: déterminer si une valeur v figure dans un tableau A de n éléments, et si oui à quelle position.
RechercheSequentielle(A, v)
pour i de 1 à A.longueur faire
si A[i] = v alors retourner i fin si
fin pour
retourner ABSENT // sentinelle: v ne figure pas dans A
L'invariant est: au début du tour i, la valeur v ne figure pas dans A[1..i−1]. Il est vrai au départ (préfixe vide) et conservé par le test. Si la boucle s'achève sans retour, l'invariant avec i=n+1 dit que v n'est nulle part: la réponse «absent» est justifiée. La terminaison est acquise, la boucle étant bornée.
Le coût, en nombre de comparaisons:
meilleur cas: 1 comparaison, la valeur est en tête — Θ(1);
pire cas: n comparaisons, la valeur est en queue ou absente — Θ(n);
cas moyen, si la valeur est présente et sa position uniforme sur {1,…,n}: n1∑k=1nk=2n+1 comparaisons — Θ(n) également.
Sur le tableau du cours, chercher 9 coûte 5 comparaisons (il est en cinquième position), chercher 100 en coûte 7 et échoue, et la moyenne sur les sept valeurs présentes vaut (7+1)/2=4. Le pire cas et le cas moyen sont dans la même classe: diviser le travail moyen par deux ne change pas la nature du problème.
Ces trois nombres disent aussi que le cas moyen ne sauve pas la recherche séquentielle. Sur un million d'éléments, elle fait 106 comparaisons dans le pire cas, soit cinquante mille fois plus que les 20 comparaisons qui suffiraient à une recherche dichotomique — à condition que le tableau soit trié, ce que la recherche séquentielle n'exige pas. C'est l'objet du chapitre 3, avec la récursivité et le principe «diviser pour régner»: la dichotomie, le tri fusion, et le théorème qui donne d'un coup le coût de tous les algorithmes de cette forme. Retenez pour l'instant l'ordre de grandeur: Θ(n) contre Θ(logn), un million contre vingt.
Ce que la vue asymptotique ne voit pas
L'analyse asymptotique est un outil de tri des idées, pas un oracle. Trois de ses angles morts méritent d'être connus, et le troisième se calcule.
Les constantes existent
O, Ω et Θ ignorent délibérément les facteurs constants. Or, à classe égale, un algorithme peut être dix ou cent fois plus lent qu'un autre. Le tri fusion du chapitre 3 est en Θ(nlogn), mais il alloue un tableau auxiliaire et recopie des données; certaines de ses variantes en place, de même classe, sont deux fois plus lentes en pratique. Entre deux algorithmes de même classe, la notation asymptotique ne tranche pas: il faut mesurer, sur des données représentatives et sur la machine visée.
Ce n'est pas un défaut de la théorie, c'est sa définition. Elle répond à «comment le coût évolue-t-il quand les données grandissent?», pas à «lequel des deux dois-je écrire aujourd'hui?».
La hiérarchie mémoire
Le modèle RAM suppose qu'accéder à A[1] et à A[1000000] coûte la même chose. C'est faux d'un facteur qui n'a rien de négligeable: sur un processeur actuel, un accès servi par le cache de premier niveau et un accès qui doit descendre en mémoire centrale diffèrent de deux ordres de grandeur environ. Deux algorithmes en Θ(n) dont l'un parcourt la mémoire dans l'ordre et l'autre par sauts imprévisibles ne se comportent pas de la même façon, et l'écart se voit au chronomètre alors qu'il est invisible dans le comptage d'opérations.
Cette différence est, elle aussi, un facteur constant — le modèle n'est donc pas «faux», il est aveugle à quelque chose d'important. Nous ne la modéliserons pas dans ce cours; retenez seulement qu'entre deux algorithmes de même classe, celui qui respecte la localité des accès gagne en général.
Un algorithme en n log n peut perdre contre un algorithme quadratique
C'est l'angle mort le plus instructif, parce qu'il se quantifie. La définition de O contient «à partir d'un certain rang n0»; rien n'interdit à n0 d'être grand.
C'est exactement ce que font les bibliothèques de tri réelles: un tri récursif rapide sur les grandes tailles, et un basculement vers le tri par insertion en dessous d'un seuil de quelques dizaines d'éléments, déterminé par mesure sur la machine visée. L'algorithme «théoriquement mauvais» n'a pas disparu; il a trouvé sa place.
Synthèse
Un algorithme est une suite finie d'instructions non ambiguës qui termine et produit la sortie spécifiée. La terminaison et la correction ne sont pas des évidences: elles se démontrent. Une recette est ambiguë, une heuristique n'est pas garantie correcte, un programme est la réalisation d'un algorithme dans un langage.
La correction d'une boucle se prouve par un invariant (vrai à l'entrée, conservé par un tour, et qui donne le résultat quand la condition de sortie devient fausse); la terminaison, par un variant, une quantité qui décroît strictement dans un ensemble bien fondé — typiquement un entier positif. L'algorithme d'Euclide se prouve ainsi: invariant gcd(a,b)=gcd(a0,b0), variant b.
On compte des opérations élémentaires, pas des secondes: le comptage est indépendant de la machine, prédictif et durable. On distingue le meilleur cas, le pire cas — la garantie — et le cas moyen, qui n'a de sens qu'avec la loi de probabilité qui le définit.
f=O(g) signifie f≤cg à partir d'un rang; Ω est la borne inférieure, Θ l'encadrement des deux côtés. O est une borne supérieure, il cache la constante, et il ne dit rien de la rapidité sur une entrée donnée. Utilisez Θ dès que vous connaissez l'ordre exact.
Sur le tableau du cours, exécution faite: le tri par sélection fait 21 comparaisons (toujours n(n−1)/2, quel que soit le tableau) et 5 échanges; le tri par insertion fait 15 comparaisons et 11 décalages, entre son meilleur cas (6) et son pire cas (21), et à un dixième de son cas moyen (14,907). La recherche séquentielle coûte Θ(n) dans le pire cas comme en moyenne.
À 109 opérations par seconde — une hypothèse, pas une mesure —, une seconde traite n=109 en linéaire, 39620077 en quasi-linéaire, 31622 en quadratique, 1000 en cubique, 29 en exponentiel et 12 en factoriel. Mais la classe n'est pas tout: avec les constantes 50nlog2n et , le tri quadratique gagne jusqu'à .
Série d'exercices du chapitre 2Exercice 1 sur 5
Question 2.8
Un algorithme effectue exactement 7n+300 opérations sur une entrée de taille n. Laquelle de ces affirmations est la plus informative et vraie?
Problème guidé 2.1 · Le maximum et le deuxième maximum
On veut trouver simultanément le plus grand et le deuxième plus grand élément d'un tableau de n éléments deux à deux distincts. On compte uniquement les comparaisons entre éléments du tableau. On travaillera sur le tableau du cours, [38,27,43,3,9,82,10], pour lequel n=7, le maximum est 82 et le deuxième maximum est 43.
1
Le maximum seul
Un simple parcours retient le plus grand élément vu jusqu'ici. Combien de comparaisons effectue-t-il sur un tableau de n=7 éléments?
Question
Nombre de comparaisons pour trouver le maximum d'un tableau de 7 éléments.
La méthode naïve en deux passes
La méthode du tournoi
Sur un grand tableau
Exercices
Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.
Exercice 2.1 · L'algorithme d'Euclide à la main
Calculer gcd(252,198) par l'algorithme d'Euclide en écrivant chaque division, et donner le nombre de divisions.
Calculer gcd(8633,5797) de la même manière. Que conclure sur ces deux nombres?
Calculer gcd(233,144). Ces deux nombres sont des termes consécutifs de la suite de Fibonacci. Combien de divisions? Comparer au point 1 et commenter.
Montrer que si a≥b≥1, alors amodb<a/2. En déduire qu'après deux tours de boucle, la première variable a été au moins divisée par deux, puis une majoration du nombre de divisions en fonction de a.
Solution
1. Les divisions successives:
252=1⋅198+54,198=3⋅54+36,54=1⋅36+18,36=2⋅18+0.
Exercice 2.2 · Invariant et variant de l'exponentiation rapide
L'algorithme suivant calcule xn pour n≥0 entier:
Puissance(x, n)
r ← 1 ; b ← x ; e ← n
tant que e > 0 faire
si e est impair alors r ← r × b fin si
b ← b × b
e ← e div 2 // division entière
fin tant que
retourner r
Exécuter l'algorithme sur x=3, n=13 en donnant la valeur de (r,b,e) au début de chaque tour.
Proposer un invariant de boucle et prouver la correction de l'algorithme.
Donner un variant et prouver la terminaison.
Compter le nombre de multiplications effectuées et le comparer à la méthode naïve. Quelle est la classe de complexité en fonction de n?
Solution
1. L'écriture binaire de 13 est (1101)2. Les valeurs au début de chaque tour, obtenues en exécutant l'algorithme:
tour
r
b
e
e impair?
1
1
3
13
oui
2
3
9
6
non
3
3
81
3
oui
4
243
6 561
1
Exercice 2.3 · Manipuler les notations asymptotiques
Pour chacune des affirmations suivantes, dire si elle est vraie ou fausse et le justifier — en exhibant c et n0 si elle est vraie, en exhibant une contradiction sinon.
2n+1=O(2n).
22n=O(2n).
n2=O(n3) et n3=O(n2).
log2n=Θ(lnn).
(n+1)!=O(n!).
Si f(n)=O(g(n)) et g(n)=O(h(n)), alors f(n)=O(h(n)).
Solution
1. Vraie.2n+1=2⋅2n, donc l'inégalité 2n+1≤c⋅2n est satisfaite avec et . Une constante multiplicative est exactement ce que absorbe.
Exercice 2.4 · Compter sur un petit tableau
On considère le tableau B=[5,1,4,2,8].
Dérouler le tri par sélection sur B: donner le tableau après chaque tour, le nombre de comparaisons et le nombre d'échanges.
Dérouler le tri par insertion sur B: donner le tableau après chaque étape et le nombre de comparaisons de chacune.
Lequel des deux gagne ici? Construire un tableau de 5 éléments sur lequel le tri par insertion fait le plus de comparaisons possible, et un sur lequel il en fait le moins.
Pour quelles valeurs de n le tri par insertion fait-il, dans le pire cas, plus de comparaisons que le tri par sélection?
Solution
1. Tri par sélection (comptages obtenus en exécutant l'algorithme):
tour
tableau après le tour
échange
départ
5, 1, 4, 2, 8
—
i=1
1, 5, 4, 2, 8
oui
i=2
1, 2, 4, 5, 8
oui
i=3
1, 2, 4, 5, 8
non
i=4
1, 2, 4, 5, 8
non
10 comparaisons (5⋅4/2=10, conformément à (2.5)) et .
Exercice 2.5 · Choisir entre deux algorithmes
Un laboratoire dispose de deux implémentations de tri, dont les coûts mesurés en opérations élémentaires sont modélisés par
CA(n)=40nlog2netCB(n)=3n2.
(Ce sont des modèles de travail, pas des mesures.)
Calculer les deux coûts pour n=16, n=64 et n=1024, et dire lequel gagne à chaque fois.
Déterminer, numériquement, la taille n∗ à partir de laquelle A devient le meilleur des deux.
À 109 opérations par seconde, combien de temps chaque implémentation met-elle pour ?
Solution
1. Avec log216=4, log264=6 et log21024=10:
Références
Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C., Introduction to Algorithms, 4e éd., MIT Press, Cambridge, chap. 1–3 (algorithmes, invariants de boucle, notations asymptotiques) et chap. 2.1–2.2 (tri par insertion).
Knuth, D. E., The Art of Computer Programming, vol. 1 (Fundamental Algorithms), 3e éd., Addison-Wesley, section 1.1 (définition d'un algorithme) et section 1.2.1 (démonstrations par récurrence appliquées aux programmes).
Knuth, D. E., The Art of Computer Programming, vol. 3 (Sorting and Searching), 2e éd., Addison-Wesley, section 5.2.1 (tri par insertion) et 5.2.3 (tri par sélection).
Sipser, M., Introduction to the Theory of Computation, 3e éd., Cengage, chap. 7.1 (mesure de complexité, notations asymptotiques).
Abelson, H., Ledeen, K. et Lewis, H., Blown to Bits, Addison-Wesley, chap. 1 (ce que les algorithmes rendent possible, et à quel prix).
Polycopiés du cours ICC de l'EPFL, partie «Algorithmique et complexité».
Trois divisions
1071=3⋅7⋅51=3⋅7⋅3⋅17
ad>0
P(n)=Θ(nd)
c2=10
n0=1
n=1,…,19
n=1
f(1)=10
f(5)=102>4⋅25=100
f(6)=140≤4⋅36=144
(c2,n0)
existe
n
O
7!=5040
2087/140=14,9071…
20
n=106
9,97⋅108
2⋅1012
fusion
n=23
2n2
n=189
Le dernier reste non nul est 18, donc gcd(252,198)=18, en 4 divisions. Vérification: 252=18⋅14 et 198=18⋅11, avec gcd(14,11)=1.
Soit 8 divisions et gcd(8633,5797)=1: les deux nombres sont premiers entre eux. Notez qu'Euclide l'établit sans factoriser ni l'un ni l'autre — et de fait 8633=89⋅97 et 5797=11⋅17⋅31, factorisations qu'il n'a jamais eu besoin de connaître.
soit 11 divisions pour gcd(233,144)=1. Les restes parcourent la suite de Fibonacci à l'envers: 89,55,34,21,13,8,5,3,2,1. C'est le pire cas de l'algorithme: quand tous les quotients valent 1, chaque division ne fait décroître les nombres que du facteur φ=(1+5)/2≈1,618, le minimum possible. Comparé au point 1, où des nombres du même ordre de grandeur (252 contre 233) n'ont demandé que 4 divisions, cela montre que le nombre de divisions dépend de la structure arithmétique des entrées, pas seulement de leur taille: 4 est ici le meilleur cas observé, 11 le pire.
4. Soit r=amodb, donc 0≤r<b. Deux cas. Si b≤a/2, alors r<b≤a/2. Si b>a/2, alors a/b<2, donc le quotient de la division de a par b vaut 1 (il vaut au moins 1 car a≥b), et r=a−b<a−a/2=a/2. Dans les deux cas r<a/2.
Un tour de boucle remplace (a,b) par (b,amodb); le tour suivant remplace ce couple par (amodb,…). La première variable, qui valait a, vaut donc amodb<a/2 deux tours plus tard: elle est au moins divisée par deux tous les deux tours. Partant de a0, elle atteint 0 après au plus 2log2a0 tours, donc l'algorithme effectue au plus 2log2a0 divisions. Pour a0=1071, cela donne au plus 20 divisions, contre le majorant grossier b0=462 du théorème 2.2 et les 3 divisions réellement effectuées. Le coût d'Euclide est donc O(loga0): logarithmique en la valeur, donc linéaire en le nombre de chiffres — c'est ce qui le rend utilisable sur les entiers de 2048 bits du chapitre 9.
oui
À la sortie, r=243⋅6561=1594323=313. Vérification: 313=1594323.
2. Invariant: r⋅be=xn.
Initialisation: avant le premier tour, r⋅be=1⋅xn=xn.
Conservation: soit (r,b,e) au début d'un tour, avec e>0 et rbe=xn. Si e=2k est pair, le tour ne touche pas r et produit (r,b2,k), d'où r(b2)k=rb2k=rbe=xn. Si e=2k+1 est impair, le tour produit (rb,b2,k), d'où (rb)(b2)k=rb2k+1=rbe=xn. Dans les deux cas l'invariant est conservé.
Terminaison de la preuve: la boucle s'arrête quand e=0; l'invariant donne alors r⋅b0=r=xn, qui est bien la valeur retournée.
3. Variant: V=e, entier positif ou nul. À chaque tour, e devient ⌊e/2⌋, et pour e≥1 on a ⌊e/2⌋<e: la décroissance est stricte dans N, bien fondé. La boucle termine donc. Plus précisément, e est au moins divisé par deux à chaque tour, donc il y a exactement ⌊log2n⌋+1 tours pour n≥1.
4. Chaque tour fait une élévation au carré, et une multiplication supplémentaire lorsque le bit courant vaut 1. Pour n=13=(1101)2: 4 tours, donc 4 carrés, et 3 bits à 1, donc 3 multiplications utiles: 7 multiplications au total (exécution vérifiée). La méthode naïve x×x×⋯×x en demande n−1=12.
En général, le nombre de multiplications est compris entre ⌊log2n⌋+1 (un seul bit à 1) et 2(⌊log2n⌋+1) (tous les bits à 1): l'algorithme est en Θ(logn) multiplications, contre Θ(n) pour la méthode naïve. Pour n=100, il fait 7 carrés et 3 multiplications, soit 10 au lieu de 99. Attention toutefois: si x est un grand entier, les multiplications ne sont pas des opérations élémentaires et leur coût croît avec la taille des opérandes — c'est pourquoi, en cryptographie, on travaille modulo n (chapitre 9), ce qui borne la taille des facteurs.
c=2
n0=0
O
2. Fausse.22n=(2n)2, donc 2n22n=2n→∞. Supposons qu'il existe c et n0 avec 22n≤c2n pour n≥n0; alors 2n≤c pour tout n≥n0, ce qui est faux dès que n>log2c. La morale: dans un exposant, un facteur constant n'est pas un facteur constant.
3.n2=O(n3) est vraie (n2≤1⋅n3 pour n≥1). n3=O(n2) est fausse: n3≤cn2 donnerait n≤c pour tout n≥n0, absurde. La relation O n'est pas symétrique; c'est une relation de domination.
4. Vraie. Par la formule de changement de base, log2n=ln2lnn, donc c1=c2=1/ln2≈1,4427 conviennent, avec n0=2. C'est pourquoi on n'écrit jamais la base d'un logarithme dans une classe de complexité: Θ(logn) ne dépend pas de la base. En revanche, dans ce cours, on écrit toujours log2 quand on compte des comparaisons ou des bits, car la constante, elle, compte.
5. Fausse.(n+1)!=(n+1)⋅n!, donc n!(n+1)!=n+1→∞: aucun c ne majore n+1 à partir d'un rang. Contrairement au point 1, le facteur qui apparaît n'est pas constant, il grandit.
6. Vraie (transitivité). Il existe c1,n1 avec f(n)≤c1g(n) pour n≥n1, et c2,n2 avec g(n)≤c2h(n) pour n≥n2. Alors, pour n≥max(n1,n2),
f(n)≤c1g(n)≤c1c2h(n),
ce qui est la définition avec c=c1c2 et n0=max(n1,n2). C'est cette transitivité qui autorise les chaînes du type «cet algorithme fait au plus autant d'opérations que celui-là, qui est en O(nlogn), donc il est en O(nlogn)».
2 échanges
2. Tri par insertion:
étape
élément inséré
tableau après l'étape
comparaisons
i=2
1
1, 5, 4, 2, 8
1
i=3
4
1, 4, 5, 2, 8
2
i=4
2
1, 2, 4, 5, 8
3
i=5
8
1, 2, 4, 5, 8
1
Total: 1+2+3+1=7 comparaisons et 4 décalages.
3. Le tri par insertion gagne: 7 contre 10. Le pire cas est le tableau strictement décroissant, par exemple [8,5,4,2,1]: chaque élément traverse tout le préfixe, soit 1+2+3+4=10=n(n−1)/2 comparaisons. Le meilleur cas est le tableau croissant [1,2,4,5,8]: chaque étape s'arrête à sa première comparaison, soit n−1=4 comparaisons.
4.Jamais, au sens strict. Le pire cas du tri par insertion vaut n(n−1)/2, exactement le nombre de comparaisons du tri par sélection, qui ne dépend pas de l'entrée. Les deux sont donc égaux dans le pire cas pour tout n, et le tri par insertion est strictement meilleur sur toute autre entrée. Ce qui départage vraiment les deux algorithmes est ailleurs: le tri par sélection fait au plus n−1 échanges, le tri par insertion jusqu'à n(n−1)/2 décalages. Si comparer est bon marché et déplacer coûteux, la sélection l'emporte; dans le cas usuel d'un tableau en mémoire, c'est l'insertion.
n=106
On envisage un algorithme hybride qui utilise B en dessous d'un seuil s et A au-dessus. Quel seuil choisir, et que faut-il faire avant de figer cette valeur dans le code?
n
CA(n)=40nlog2n
CB(n)=3n2
vainqueur
16
40⋅16⋅4=2560
3⋅256=768
B
64
40⋅64⋅6=15360
2. On cherche le plus petit n tel que 40nlog2n≤3n2, c'est-à-dire, en divisant par n>0,
40log2n≤3n⟺n≥340log2n.
La fonction h(n)=n−340log2n est négative en n=64 (64−80=−16) et positive en n=128 (128−93,33=34,67); par dichotomie, sa racine vaut n∗=85,59…. Le premier entier pour lequel A l'emporte est donc n=86: CA(86)=40⋅86⋅log286=22106 contre CB(86)=3⋅862=22188, soit un écart de 0,37% seulement. À n=87, l'écart n'est encore que de 1,26% (22421 contre 22707). Près du seuil, un modèle de coût n'est pas assez précis pour trancher — et c'est une information en soi.
3. Pour n=106, log2106=19,93:
CA=40⋅106⋅19,93=7,97⋅108opeˊrations≈0,80s,
CB=3⋅1012opeˊrations≈3000s≈50minutes.
Le rapport est de 3763: c'est la différence entre «une seconde» et «on repasse après le déjeuner».
4. Un seuil de l'ordre de s≈86 est cohérent avec le modèle. Mais avant de le figer, il faut mesurer — pour trois raisons développées dans le chapitre. D'abord, les constantes 40 et 3 sont des modèles: elles dépendent de la machine, du compilateur et du type des données triées, et un facteur 2 sur l'une déplace le seuil de plusieurs dizaines. Ensuite, le modèle RAM ignore la hiérarchie mémoire, qui favorise B tant que les données tiennent en cache — donc précisément dans la zone du seuil. Enfin, près du seuil les deux coûts diffèrent de moins d'un pour cent: n'importe quelle valeur de s entre 60 et 120 donnera des performances quasi identiques, et il est inutile de se battre pour la troisième décimale. La bonne pratique est de mesurer sur des données représentatives, de choisir un seuil dans le plat de la courbe, et de documenter l'hypothèse dans le code.