NSI, Terminale • Exercices corrigés à Montréal

Fiche de révision : algorithmique et complexité (NSI Terminale)

Q: Pourquoi la recherche dichotomique exige-t-elle un tableau trié ?

Parce qu'elle compare la valeur cherchée au seul élément du milieu et en déduit dans quelle moitié continuer. Cette déduction n'est valable que si l'ordre est garanti partout : sur un tableau quelconque, elle élimine une moitié qui pouvait contenir la valeur et répond que l'élément est absent, sans planter et sans avertissement.

Q: Quelle différence entre un invariant et un variant de boucle ?

L'invariant est une propriété vraie avant la boucle et préservée par chaque tour : il prouve que le résultat est correct. Le variant est un entier positif qui diminue strictement à chaque tour : il prouve que la boucle s'arrête. Un contrôle demande souvent les deux, et donner l'un à la place de l'autre ne rapporte aucun point.

Q: Le tri par insertion est-il toujours meilleur que le tri par sélection ?

Non. Sur un tableau déjà trié ou presque, l'insertion est nettement plus rapide car elle s'arrête tôt à chaque étape. Mais dans le pire cas les deux font le même nombre de comparaisons, et la sélection garde un avantage quand les échanges coûtent cher, puisqu'elle en fait au plus un par tour.

Q: Que signifie exactement une complexité en grand O ?

Elle décrit l'ordre de grandeur du nombre d'opérations quand la taille des données devient grande, en ignorant les constantes et les termes secondaires. Un algorithme en grand O de n au carré voit son temps multiplié par quatre quand la taille double. Sur de petites données, un algorithme théoriquement moins bon peut rester plus rapide.

Q: Pourquoi le calcul récursif de Fibonacci est-il si lent ?

Parce que chaque appel en déclenche deux, et que les mêmes valeurs sont recalculées un nombre exponentiel de fois. Pour le trentième terme, cela représente environ deux millions sept cent mille appels, contre trente tours pour une simple boucle. Mémoriser les valeurs déjà calculées ramène le coût à quelque chose de linéaire.

Q: Un algorithme glouton donne-t-il toujours la meilleure solution ?

Non, et c'est précisément ce que les contrôles font vérifier. Avec un système de pièces valant un, trois et quatre, rendre six par la méthode gloutonne donne quatre plus un plus un, soit trois pièces, alors que deux pièces de trois suffisent. Pour affirmer qu'un glouton est optimal, il faut le démontrer sur le cas précis de l'énoncé.

L'algorithmique de NSI ne demande presque jamais d'écrire un programme long. Elle demande de COMPTER : combien de comparaisons, combien de tours, et ce que devient ce nombre quand la taille des données double. Les points se perdent presque tous sur ce comptage, jamais sur la syntaxe Python.

Cette fiche liste les huit erreurs qui reviennent en contrôle, avec la phrase exacte qui les remet, l'arbre de lecture d'un code pour en déduire sa complexité, et une recherche dichotomique décortiquée jusqu'à sa preuve de correction et de terminaison.

Le fil du chapitre

Une complexité ne se devine pas au ressenti, elle se COMPTE : on compte les tours de boucle et les comparaisons, puis on ne garde que l'ordre de grandeur, et c'est ce comptage que le barème note.

Ce chapitre fait partie de NSI en Terminale

Avant ce chapitre

Cette fiche suppose ces notions acquises. Si une méthode ci-dessous reste opaque, c'est presque toujours l'une d'elles qui manque, pas la fiche.

Algorithmique : preuve, terminaison et coûtPremière Fiche

Remonter plus loin : la chaîne complète (4 chapitres) ↓

Le chemin de remédiation, du plus ancien au plus proche. Un élève qui reprend ce chapitre de zéro le reprend dans cet ordre.

1Algorithmique et PythonSeconde, Mathématiques
2Python : types, contrôle, fonctions et tableauxPremière
3Algorithmique : preuve, terminaison et coûtPremière
4Algorithmique et ScratchTroisième, Mathématiques

L'essentiel

Les cinq coûts à connaître par coeur

• Recherche SÉQUENTIELLE dans un tableau de $n$ éléments : au pire $n$ comparaisons, coût $O(n)$ . Aucune hypothèse sur le tableau.
• Recherche DICHOTOMIQUE : environ $\log_{2}n$ comparaisons, coût $O(\log n)$ . Elle exige un tableau TRIÉ, sans exception.
• Tri par SÉLECTION : exactement $\frac{n(n-1)}{2}$ comparaisons, quel que soit le tableau, et au plus $n-1$ échanges.
• Tri par INSERTION : $\frac{n(n-1)}{2}$ comparaisons au pire, mais seulement $n-1$ si le tableau est déjà trié.

Les quatre courbes se confondent près de l’origine, et c’est plus loin que l’écart devient irrattrapable. En abscisse la taille

n

: à

n=20

le logarithme vaut

4

, le carré vaudrait

400

Les deux tris sont en $O(n^{2})$ , mais l'insertion est en $O(n)$ sur un tableau déjà presque trié, alors que la sélection ne profite jamais de rien. C'est la seule différence que le barème demande.

Ce que la notation grand O garde et ce qu'elle jette

• On garde le TERME DOMINANT et l'on jette les constantes : $3n^{2}+100n+7$ est en $O(n^{2})$ .
• L'ordre de grandeur décrit le comportement quand $n$ devient GRAND. Pour $n=10$ , un algorithme en $O(n^{2})$ peut être plus rapide qu'un $O(n\log n)$ .
• Boucles IMBRIQUÉES qui parcourent chacune le tableau : les coûts se MULTIPLIENT, donc $O(n^{2})$ . Boucles successives : ils s'ADDITIONNENT, donc $O(n)$ .
• Une taille qui double multiplie le temps par $2$ en $O(n)$ , par $4$ en $O(n^{2})$ , et n'ajoute qu'UNE comparaison en $O(\log n)$ .

Prouver un algorithme : deux outils distincts

• L'INVARIANT prouve la CORRECTION : c'est une propriété vraie avant la boucle, préservée par chaque tour, et qui donne le résultat voulu à la sortie.
• Le VARIANT prouve la TERMINAISON : c'est un entier positif qui DÉCROÎT strictement à chaque tour, donc la boucle ne peut pas tourner indéfiniment.
• Une preuve d'invariant se rédige en trois temps : initialisation, conservation, conclusion à la sortie de boucle.
• Un algorithme peut être correct et ne jamais s'arrêter : les deux preuves sont indépendantes, et un contrôle demande souvent les deux.

Récursivité et gloutons, les deux pièges de fin de chapitre

• Une fonction récursive a besoin d'un CAS DE BASE atteint par tous les appels, sinon la pile déborde.
• La récursivité naïve de Fibonacci recalcule les mêmes valeurs des millions de fois : son coût est EXPONENTIEL, pas linéaire.
• Un algorithme GLOUTON prend à chaque étape le meilleur choix local, sans jamais revenir en arrière. Il est rapide, souvent en $O(n)$ ou $O(n\log n)$ .
• Un glouton n'est PAS toujours optimal : il faut soit le prouver, soit exhiber un contre-exemple. Le rendu de monnaie en est l'exemple canonique.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Lancer une dichotomie sur un tableau non trié

toute la question, et l'algorithme rend un résultat faux sans planter

Ce qu'il ne faut pas écrire

« La recherche dichotomique est plus rapide, donc je l'utilise sur ce tableau de relevés. »

Ce qu'il faut écrire

« La dichotomie exige un tableau TRIÉ : sinon elle élimine une moitié qui pouvait contenir la valeur, et elle répond faux. Ici le tableau n'est pas trié, donc c'est la recherche séquentielle, en $O(n)$ . »

Pourquoi : La dichotomie ne compare qu'à l'élément du milieu et déduit de cette seule comparaison dans quelle moitié chercher. Cette déduction n'est valable que si l'ordre est garanti partout.

2. Croire que le tri par sélection coûte moins cher sur un tableau déjà trié

1 à 2 points, sur la question de comptage exact

Ce qu'il ne faut pas écrire

« Le tableau est déjà trié, donc le tri par sélection s'arrête tout de suite. »

Ce qu'il faut écrire

« Le tri par sélection fait TOUJOURS $\frac{n(n-1)}{2}$ comparaisons, trié ou non : il cherche le minimum du reste à chaque tour, donc il parcourt tout le reste. Seul le nombre d'ÉCHANGES tombe à zéro. »

Pourquoi : L'algorithme n'a aucun test d'arrêt anticipé : sa boucle interne va jusqu'au bout du tableau à chaque tour. C'est précisément ce qui le distingue du tri par insertion.

3. Confondre l'invariant et le variant

toute la question de preuve, soit souvent 3 points

Ce qu'il ne faut pas écrire

« L'invariant de boucle est $i<n$ , qui décroît jusqu'à devenir faux. »

Ce qu'il faut écrire

« $n-i$ est le VARIANT : entier positif qui décroît strictement, il prouve la TERMINAISON. L'invariant est une propriété comme : le sous-tableau des $i$ premières cases est trié, et il prouve la CORRECTION. »

Pourquoi : Les deux objets répondent à deux questions différentes : est-ce que ça s'arrête, et est-ce que ce qui sort est juste. Une copie qui donne l'un à la place de l'autre ne répond pas à la question posée.

4. Croire qu'un doublement de la taille double le temps en O(n²)

1 à 2 points, sur la question d'estimation

Ce qu'il ne faut pas écrire

« L'algorithme est en $O(n^{2})$ et met $2$ secondes pour $1\,000$ éléments, donc il mettra $4$ secondes pour $2\,000$ . »

Ce qu'il faut écrire

« En $O(n^{2})$ , doubler $n$ multiplie le temps par $2^{2}=4$ : il mettra environ $8$ secondes. Le facteur est le CARRÉ du facteur d'agrandissement. »

Pourquoi : Le coût est proportionnel à $n^{2}$ , donc passer de $n$ à $2n$ le multiplie par $\frac{(2n)^{2}}{n^{2}}=4$ . Le même raisonnement donne $9$ pour un triplement, et $100$ pour un facteur $10$ .

5. Prendre la récursivité naïve de Fibonacci pour un algorithme linéaire

toute la question, et un programme qui ne rend jamais la main en TP

Ce qu'il ne faut pas écrire

« La fonction fait un seul parcours des entiers jusqu'à $n$ , donc elle est en $O(n)$ . »

Ce qu'il faut écrire

« Chaque appel en déclenche DEUX, donc le nombre d'appels est de l'ordre de $2^{n}$ . Pour $n=30$ cela fait environ $2{,}7$ millions d'appels, contre $30$ tours pour la version itérative. »

Chaque tour de la dichotomie coupe l'intervalle en deux :

16

8

4

2

1

. Quatre tours suffisent, et doubler la taille du tableau n'en ajoute qu'un seul.

Pourquoi : L'arbre des appels se dédouble à chaque niveau, et les mêmes valeurs sont recalculées un nombre exponentiel de fois. La mémoïsation, ou une simple boucle, ramène le coût à $O(n)$ .

6. Déclarer un algorithme glouton optimal sans le prouver

toute la question, car c'est exactement la question posée

Ce qu'il ne faut pas écrire

« On prend toujours la plus grosse pièce possible, donc on obtient le nombre minimal de pièces. »

Ce qu'il faut écrire

« Le glouton donne une solution valide, pas nécessairement optimale. Avec le système $\{1\,;3\,;4\}$ et une somme de $6$ , il rend $4+1+1$ , soit $3$ pièces, alors que $3+3$ n'en demande que $2$ . »

Les deux lignes rendent la même somme

6

. Le glouton prend d'abord la pièce de

4

et se condamne à deux pièces de

1

; la solution optimale renonce à ce premier choix.

Pourquoi : Un choix localement optimal peut fermer la porte à une meilleure combinaison globale. Le glouton est optimal pour le système monétaire canadien, mais cette propriété dépend du système et doit être démontrée.

7. Oublier de décaler la borne dans la dichotomie

toute la question, et une boucle infinie à la démonstration

Ce qu'il ne faut pas écrire

« Si l'élément cherché est plus grand, alors debut prend la valeur $m$ . »

Ce qu'il faut écrire

« Il faut $debut=m+1$ , et $fin=m-1$ dans l'autre cas. Avec $debut=m$ , l'intervalle cesse de diminuer dès qu'il ne reste que deux cases, et la boucle tourne indéfiniment. »

Pourquoi : Le variant $fin-debut$ doit décroître STRICTEMENT à chaque tour. Réaffecter la borne à $m$ sans le décalage laisse le variant inchangé, et la preuve de terminaison s'effondre avec le programme.

8. Additionner les coûts de deux boucles imbriquées

1 à 2 points, et la comparaison d'algorithmes qui suit devient fausse

Ce qu'il ne faut pas écrire

« Il y a deux boucles qui parcourent le tableau, donc le coût est $n+n=2n$ , soit $O(n)$ . »

Ce qu'il faut écrire

« Des boucles IMBRIQUÉES se MULTIPLIENT : la boucle interne tourne $n$ fois pour CHAQUE tour de l'externe, donc $n\times n=n^{2}$ , soit $O(n^{2})$ . C'est l'indentation qui tranche, pas le nombre de boucles. »

Pourquoi : Deux boucles SUCCESSIVES, l'une après l'autre au même niveau d'indentation, donnent bien $O(n)$ . Le seul indice fiable dans un code Python est la colonne où commence chaque `for`.

Quelle méthode choisir

Quelle complexité selon la forme du code

On lit la structure du code, pas ce qu'il calcule.

Si aucune boucle, un nombre fixe d'opérations → $O(1)$ , coût constant

Exemple : lire une case d'un tableau, échanger deux valeurs
Si une boucle qui parcourt les $n$ éléments → $O(n)$ , coût linéaire
Si une boucle où la zone de recherche est DIVISÉE PAR DEUX à chaque tour → $O(\log n)$

C'est la signature de la dichotomie : une division, pas une soustraction.
Si deux boucles IMBRIQUÉES parcourant chacune le tableau → $O(n^{2})$ , coût quadratique

Exemple : les tris par sélection et par insertion
Si chaque appel récursif en déclenche DEUX, sans mémoïsation → $O(2^{n})$ , coût exponentiel, inutilisable au-delà de $n\approx 40$
Si on découpe en deux moitiés que l'on traite puis que l'on fusionne → $O(n\log n)$ , le coût des tris efficaces

Le repère qui tranche entre $O(n)$ et $O(\log n)$ : regardez comment la variable de boucle évolue. Si elle est DIVISÉE, c'est un logarithme; si elle est incrémentée, c'est linéaire.

Quel algorithme de recherche ou de tri choisir

L'énoncé décrit les données et le nombre de requêtes : c'est cela qui décide.

Si le tableau n'est pas trié et on cherche une seule fois → recherche SÉQUENTIELLE : trier coûterait plus cher que la recherche elle-même
Si le tableau est trié, ou on va chercher très souvent dedans → recherche DICHOTOMIQUE, quitte à trier une fois au départ
Si le tableau est déjà presque trié → tri par INSERTION : il descend à $O(n)$ dans ce cas, la sélection non
Si les échanges coûtent très cher et les comparaisons non → tri par SÉLECTION : au plus $n-1$ échanges, contre bien davantage pour l'insertion
Si on demande une solution rapide et pas forcément la meilleure → algorithme GLOUTON, en signalant explicitement qu'il n'est pas prouvé optimal
Si on demande la solution OPTIMALE avec preuve → il faut soit démontrer que le glouton l'est, soit explorer toutes les possibilités

Une question de choix attend toujours une JUSTIFICATION chiffrée, du type : trier coûte $n\log n$ puis chaque recherche coûte $\log n$ , ce qui devient rentable dès la centième requête.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Prouver la correction d'une boucle par un invariant

Quand l'utiliser : Dès que l'énoncé dit « démontrer que l'algorithme est correct » ou « donner un invariant de boucle ».

1 ÉNONCER l'invariant sous forme de propriété, avec les variables du code : « avant chaque tour, le sous-tableau des $i$ premières cases est trié ».
2 INITIALISATION : montrer que la propriété est vraie avant le premier tour, souvent parce que le sous-tableau est vide ou réduit à une case.
3 CONSERVATION : supposer la propriété vraie avant un tour, et montrer qu'elle l'est encore après ce tour.
4 CONCLUSION : appliquer la propriété à la sortie de boucle, quand la condition d'arrêt est atteinte, pour obtenir le résultat annoncé.
5 TERMINAISON : exhiber le variant, entier positif décroissant strictement, ce qui garantit que la sortie a bien lieu.
6 Conclure par une phrase qui relie les deux : l'algorithme s'arrête, et ce qu'il renvoie est correct.

Phrase de conclusion

L'invariant est : avant chaque tour, le sous-tableau $t[0\ldots i-1]$ est trié. Il est vrai pour $i=1$ , il est conservé par l'insertion de $t[i]$ à sa place, donc à la sortie, pour $i=n$ , le tableau entier est trié.

Le piège : Donner l'invariant sans traiter les trois temps. Une propriété énoncée seule vaut souvent $0{,}5$ point sur $3$ : ce sont l'initialisation et la conservation qui font la démonstration.

Barème : 1 point pour l'invariant correctement énoncé, 0,5 pour l'initialisation, 1 pour la conservation, 0,5 pour la conclusion.

Justifier une complexité

Quand l'utiliser : « Donner la complexité de cet algorithme en justifiant » : la justification vaut plus que le résultat.

1 Dire quelle OPÉRATION on compte : comparaisons, échanges, ou appels de fonction.
2 Compter les tours de la boucle la plus externe, en fonction de $n$ .
3 Compter les tours de chaque boucle interne, puis MULTIPLIER si elles sont imbriquées.
4 Sommer et donner le nombre exact quand il est calculable, par exemple $\frac{n(n-1)}{2}$ .
5 Ne garder que le terme dominant et écrire la conclusion en grand O.
6 Préciser s'il s'agit du PIRE cas, du meilleur, ou du cas moyen, car l'énoncé le demande souvent.

Phrase de conclusion

La boucle externe effectue $n-1$ tours, et pour le tour numéro $i$ la boucle interne en effectue $n-i$ , ce qui donne $\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}$ comparaisons, soit une complexité en $O(n^{2})$ .

Le piège : Écrire seulement « c'est en $O(n^{2})$ » sans le comptage. Le résultat seul ne vaut presque rien, alors que le comptage exact, même mal conclu, rapporte l'essentiel des points.

Barème : 1 point pour l'opération comptée, 1,5 pour le comptage détaillé, 0,5 pour la conclusion en grand O.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

Vérifier l'hypothèse de tri avant toute dichotomie

Avant d'écrire ou d'invoquer une recherche dichotomique, relire l'énoncé : le tableau est-il trié ? Si l'énoncé ne le dit pas, il faut trier d'abord et compter ce coût.

Sur $[7\,;2\,;9\,;4]$ , la dichotomie compare à $9$ , part à droite et ne trouve jamais $2$ .
Tester le comptage sur un petit cas

Appliquer la formule trouvée à $n=3$ ou $n=4$ et compter à la main sur un exemple. Un écart d'un facteur $2$ ou d'un terme $n$ se voit immédiatement.

Pour $n=4$ , $\frac{4\times 3}{2}=6$ comparaisons, et le tri par sélection en fait bien $3+2+1=6$ .
Contrôler qu'un variant décroît strictement

Repérer la quantité qui doit diminuer et vérifier qu'aucun chemin du code ne la laisse inchangée. Un seul chemin sans décroissance suffit à créer une boucle infinie.

Dans la dichotomie, $fin-debut$ ne décroît que grâce aux $m+1$ et $m-1$ .
Comparer l'ordre de grandeur au bon sens

Une complexité annoncée doit résister au test du million : un $O(n)$ traite un million d'éléments en une seconde, un $O(n^{2})$ y passerait des jours.

$1\,000\,000^{2}=10^{12}$ opérations : aucun algorithme quadratique ne tourne à cette taille.
Relire l'indentation avant de conclure sur les boucles

En Python, c'est la colonne du `for` qui dit si les boucles sont imbriquées ou successives, donc si les coûts se multiplient ou s'additionnent.

Deux `for` alignés donnent $O(n)$ ; le second décalé vers la droite donne $O(n^{2})$ .

L'exercice type décortiqué

Une recherche dichotomique, comme au contrôle

On dispose d'un tableau `t` de $n$ entiers TRIÉS par ordre croissant et d'une valeur `v`. L'algorithme initialise $debut=0$ et $fin=n-1$ , puis tant que $debut\le fin$ , calcule $m=(debut+fin)//2$ , renvoie $m$ si $t[m]=v$ , pose $debut=m+1$ si $t[m]<v$ , et $fin=m-1$ sinon. Il renvoie $-1$ à la sortie de boucle.

1. Dérouler l'algorithme sur $t=[2\,;5\,;8\,;12\,;16\,;23\,;38\,;56]$ et $v=23$ . 2. Donner un variant et prouver la terminaison. 3. Donner un invariant et prouver la correction. 4. Donner la complexité. 5. Comparer à la recherche séquentielle pour $n=1\,000\,000$ .

Étape 1

Tour 1 : $debut=0$ , $fin=7$ , $m=3$ , $t[3]=12<23$ , donc $debut=4$ .

Pourquoi

La division entière $//$ arrondit vers le bas : $(0+7)//2=3$ . Le décalage à $m+1$ exclut la case déjà testée, ce qui fera décroître le variant.

Étape 2

Tour 2 : $debut=4$ , $fin=7$ , $m=5$ , $t[5]=23=v$ , donc l'algorithme renvoie $5$ .

Pourquoi

Deux comparaisons ont suffi sur huit cases. Un déroulé se rédige en tableau, une ligne par tour, avec les trois valeurs $debut$ , $fin$ et $m$ : c'est ce que le barème attend.

Étape 3

Variant : $fin-debut+1$ , le nombre de cases restantes. Il est entier, positif tant que la boucle tourne, et chaque tour le fait passer d'environ $k$ à environ $\frac{k}{2}$ , donc il décroît strictement.

Pourquoi

Il faut vérifier la décroissance sur les DEUX branches : $debut=m+1$ élimine la moitié gauche et la case du milieu, $fin=m-1$ élimine la moitié droite et la case du milieu. Aucune branche ne laisse le variant inchangé.

Étape 4

La boucle s'arrête donc au plus tard quand $fin-debut+1$ atteint $0$ , c'est-à-dire quand $debut>fin$ : la terminaison est prouvée.

Pourquoi

Un entier positif qui décroît strictement ne peut pas décroître indéfiniment. C'est l'argument standard, et il doit être écrit, pas sous-entendu.

Étape 5

Invariant : avant chaque tour, si $v$ figure dans le tableau, alors son indice appartient à l'intervalle $[debut\,;fin]$ .

Pourquoi

L'invariant doit porter sur ce que l'algorithme préserve, pas sur ce qu'il calcule. Ici, il dit que l'on n'a jamais jeté la bonne case.

Étape 6

Initialisation : $[0\,;n-1]$ contient tous les indices, l'invariant est vrai. Conservation : le tableau étant TRIÉ, si $t[m]<v$ alors aucun indice $\le m$ ne convient, donc restreindre à $[m+1\,;fin]$ préserve la propriété. Conclusion : à la sortie l'intervalle est vide, donc $v$ ne figure pas dans le tableau et $-1$ est la bonne réponse.

Pourquoi

C'est ici, et seulement ici, que l'hypothèse de tri sert. Une copie qui ne la cite pas dans la conservation n'a pas fait la démonstration, même si la conclusion est juste.

Étape 7

Complexité : le nombre de cases est divisé par deux à chaque tour, donc le nombre de tours est de l'ordre de $\log_{2}n$ , et la complexité est $O(\log n)$ .

Pourquoi

La signature d'un logarithme est une DIVISION par deux, jamais une soustraction. Une boucle qui retirerait une case à chaque tour serait en $O(n)$ .

Étape 8

Pour $n=1\,000\,000$ : $\log_{2}(10^{6})\approx 19{,}9$ , donc au plus $20$ comparaisons, contre $1\,000\,000$ au pire pour la recherche séquentielle, soit un rapport de $50\,000$ .

Pourquoi

Le chiffre frappe et il est attendu par le barème. Il montre aussi pourquoi il vaut la peine de trier une fois, en $n\log n$ , quand on doit chercher souvent.

Conclusion rédigée

L'algorithme renvoie $5$ , il termine grâce au variant $fin-debut+1$ , il est correct grâce à l'invariant qui confine l'indice cherché à l'intervalle courant, et sa complexité est $O(\log n)$ : $20$ comparaisons au lieu d'un million pour un tableau de $10^{6}$ cases.

L'erreur classique sur cet exercice : Prouver la correction sans jamais mentionner que le tableau est trié. C'est l'hypothèse qui rend la conservation de l'invariant possible : sans elle, la démonstration est fausse et le barème le sanctionne comme tel.

À savoir par cœur

• Séquentielle : $O(n)$ , aucune hypothèse. Dichotomique : $O(\log n)$ , tableau TRIÉ obligatoire.
• Sélection : $\frac{n(n-1)}{2}$ comparaisons TOUJOURS, au plus $n-1$ échanges.
• Insertion : $\frac{n(n-1)}{2}$ au pire, $n-1$ si le tableau est déjà trié.
• INVARIANT pour la correction, VARIANT pour la terminaison. Ce sont deux preuves distinctes.
• Boucles imbriquées : les coûts se MULTIPLIENT. Boucles successives : ils s'ADDITIONNENT.
• Doubler $n$ multiplie le temps par $2$ en $O(n)$ , par $4$ en $O(n^{2})$ , et ajoute UNE comparaison en $O(\log n)$ .
• Une variable de boucle DIVISÉE signale un logarithme, incrémentée signale du linéaire.
• Fibonacci récursif naïf est en $O(2^{n})$ : environ $2{,}7$ millions d'appels pour $n=30$ .
• Un glouton est rapide mais pas prouvé optimal : donner le contre-exemple ou la preuve.

Questions fréquentes

Pourquoi la recherche dichotomique exige-t-elle un tableau trié ?

Parce qu'elle compare la valeur cherchée au seul élément du milieu et en déduit dans quelle moitié continuer. Cette déduction n'est valable que si l'ordre est garanti partout : sur un tableau quelconque, elle élimine une moitié qui pouvait contenir la valeur et répond que l'élément est absent, sans planter et sans avertissement.

Quelle différence entre un invariant et un variant de boucle ?

L'invariant est une propriété vraie avant la boucle et préservée par chaque tour : il prouve que le résultat est correct. Le variant est un entier positif qui diminue strictement à chaque tour : il prouve que la boucle s'arrête. Un contrôle demande souvent les deux, et donner l'un à la place de l'autre ne rapporte aucun point.

Le tri par insertion est-il toujours meilleur que le tri par sélection ?

Non. Sur un tableau déjà trié ou presque, l'insertion est nettement plus rapide car elle s'arrête tôt à chaque étape. Mais dans le pire cas les deux font le même nombre de comparaisons, et la sélection garde un avantage quand les échanges coûtent cher, puisqu'elle en fait au plus un par tour.

Que signifie exactement une complexité en grand O ?

Elle décrit l'ordre de grandeur du nombre d'opérations quand la taille des données devient grande, en ignorant les constantes et les termes secondaires. Un algorithme en grand O de n au carré voit son temps multiplié par quatre quand la taille double. Sur de petites données, un algorithme théoriquement moins bon peut rester plus rapide.

Pourquoi le calcul récursif de Fibonacci est-il si lent ?

Parce que chaque appel en déclenche deux, et que les mêmes valeurs sont recalculées un nombre exponentiel de fois. Pour le trentième terme, cela représente environ deux millions sept cent mille appels, contre trente tours pour une simple boucle. Mémoriser les valeurs déjà calculées ramène le coût à quelque chose de linéaire.

Un algorithme glouton donne-t-il toujours la meilleure solution ?

Non, et c'est précisément ce que les contrôles font vérifier. Avec un système de pièces valant un, trois et quatre, rendre six par la méthode gloutonne donne quatre plus un plus un, soit trois pièces, alors que deux pièces de trois suffisent. Pour affirmer qu'un glouton est optimal, il faut le démontrer sur le cas précis de l'énoncé.

Passer à la pratique

Exercices corrigés : Algorithmique : recherche, tris, récursivité et complexité

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

15 exercices corrigés
150 points
225 minutes

Faire les exercices

Fiche suivante Structures de données : piles, files, arbres et graphes

Ce chapitre resservira dans

Les chapitres qui le réclament en amont, plus tard dans l'année ou dans les années suivantes.

Structures de données : piles, files, arbres et graphes Récursivité, objet, mise au point et calculabilité

Voir aussi

Toutes les fiches Tous les exercices Fiche : algorithmique et complexité (NSI Première)Tutorat NSI Tuteur Première Tuteur Terminale Programme AEFE

Besoin d'un coup de main en NSI ?

Je donne des cours particuliers de NSI à Montréal, en personne ou en ligne : algorithmique, complexité, Python, structures de données et projets du programme.

Me contacter WhatsApp

Site par Studio Squalli