Fiche à trous · Première · NSI

Algorithmique — Complexité et algorithmes fondamentaux

Complétez de mémoire, puis vérifiez avec la page de corrigé.

Sur mille éléments, un algorithme quadratique fait un million d'opérations là où une recherche dichotomique en fait dix. L'écart n'est pas une question de machine rapide ou lente : c'est une loi de croissance, et aucun processeur ne la rattrape. Savoir la calculer, c'est savoir quel programme tiendra quand les données grossiront.

Ce que mesure la complexité

Règle

Piège

Comparer deux algorithmes par leur temps mesuré sur un petit jeu de données.

Comparer des lois de croissance, pas des mesures ponctuelles.

Exemple

Comparer le nombre d'opérations d'un algorithme en O(n²) et d'une recherche par dichotomie, pour n = 1 000.

Résultat :

La recherche dichotomique

Règle

Piège

Appliquer une recherche dichotomie à un tableau qui n'a pas été trié au préalable.

Avant toute dichotomie, vérifier — ou établir — que le tableau est trié.

Les tris

Propriété

Le tri fusion illustre ce qu'apporte la récursivité : la fusion de deux listes déjà triées est facile, et c'est cette facilité qu'on obtient en découpant. Il a un coût que le tri par insertion n'a pas : il utilise de la mémoire supplémentaire pour la fusion. Choisir un tri, c'est donc arbitrer entre temps et mémoire, et non désigner un vainqueur absolu.

Les graphes

Propriété

Évaluer la complexité d'un algorithme

Ai-je identifié la taille de l'entrée avant de compter ?
Ai-je compté l'imbrication des boucles, et non leur nombre ?
Ai-je ignoré les constantes dans ma notation ?
Ai-je précisé le cas — favorable, moyen, défavorable ?
Mon tableau est-il trié avant toute dichotomie ?
Ai-je vérifié que les poids sont positifs avant d'appliquer Dijkstra ?

Corrigé · à détacher

Algorithmique — Complexité et algorithmes fondamentaux

1. La complexité mesure la croissance du coût quand la taille de l'entrée augmente : c'est une loi d'évolution, pas une durée en secondes. On la note O(n) et on ignore les constantes multiplicatives et les termes de moindre ordre, parce qu'ils cessent de compter quand l'entrée grandit. Les classes usuelles, par coût croissant : O(1), O(log n), O(n), O(n log n), O(n²).
2. $O (1) < O (l o g n) < O (n) < O (n l o g n) < O (n^{2})$
3. Pour l'algorithme quadratique, l'ordre de grandeur est n × n :
4. Soit environ un million d'opérations.
5. La dichotomie divise l'espace de recherche par deux à chaque étape : il faut environ dix étapes, puisque 2 puissance 10 dépasse 1 000.
6. Soit dix opérations contre un million : le rapport est de cent mille.
7. Environ 1 000 000 contre 10
8. La dichotomie cherche une valeur en comparant à l'élément central : si la valeur cherchée est plus petite, on élimine toute la moitié droite, sinon la moitié gauche. Chaque comparaison divise par deux l'espace restant, d'où une complexité en O(log n). Elle exige une condition impérative : le tableau doit être trié.
9. $c ha q u e \overset{e}{ˊ} t a p e d i v i se l^{'} es p a ce d er ec h er c h e p a r 2$
10. Le tri par insertion construit la partie triée élément par élément, en insérant chaque nouvel élément à sa place. Sa complexité est en O(n²) dans le cas défavorable, mais il est efficace sur de petits tableaux et sur des données presque triées. Le tri fusion applique le principe « diviser pour régner » : couper le tableau en deux, trier chaque moitié, puis fusionner les deux moitiés triées. Sa complexité est en O(n log n) dans tous les cas.
11. L'algorithme de Dijkstra calcule le plus court chemin depuis un sommet de départ dans un graphe dont les arêtes portent des poids positifs. Son principe : maintenir pour chaque sommet la meilleure distance connue, traiter à chaque étape le sommet non traité le plus proche, et mettre à jour ses voisins. La condition de positivité n'est pas un détail : avec des poids négatifs, l'algorithme peut figer une distance qu'un chemin ultérieur aurait améliorée.
12. Identifier la taille de l'entrée, notée n : nombre d'éléments, de sommets, de caractères.
13. Repérer les boucles et leur imbrication : deux boucles imbriquées sur n donnent O(n²).
14. Repérer les découpages par deux : ils introduisent un logarithme.
15. Ignorer les constantes et les termes dominés : O(3n + 5) s'écrit O(n).
16. Conclure en précisant s'il s'agit du cas favorable, moyen ou défavorable.