Question transversaleMathsNSIAlgorithmes et complexité

Pourquoi trier un million de nombres peut-il prendre dix minutes ou un centième de seconde selon l'algorithme ?

Q: Que signifie la notation O(n²) ?

Le nombre d'opérations est majoré par $Cn²$ pour une constante $C$, à partir d'un certain rang.

Le tri par sélection fait n(n − 1)/2 comparaisons : 5 × 10¹¹ pour un million de nombres, soit environ 500 s à un milliard d'opérations par seconde. Le tri fusion en fait de l'ordre de n log₂ n ≈ 2 × 10⁷, soit 0,02 s. L'écart vient de la forme de la fonction, pas de la machine.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En NSI, j'ai programmé un tri par sélection qui fonctionnait très bien sur une liste de cent nombres. En le testant sur une liste d'un million de valeurs, mon ordinateur a semblé bloqué. La fonction sorted de Python, elle, répondait instantanément. J'ai voulu comprendre cette différence énorme, et les sommes de suites arithmétiques m'ont donné la réponse.

L'enjeu et les notions du programme

Dénombrer les opérations d'un algorithme par une somme, et comparer une croissance quadratique à une croissance en n ln n.

Mathématiques

Somme des termes d'une suite arithmétique (première)
Fonction logarithme, comparaison de croissances (terminale)
Ordres de grandeur, puissances de 10 (seconde)

Numérique et sciences informatiques

Tris par insertion et par sélection, coût (première)
Méthode « diviser pour régner », tri fusion (terminale)

Le plan de l'exposé en 9,5 min

1. Introduction
1 min
Le coût d'un algorithme se mesure par le nombre d'opérations élémentaires en fonction de la taille $n$ n des données. Problématique : comment ce nombre explique-t-il l'écart entre deux méthodes de tri ?
2. Mathématiques : compter les comparaisons
4 min
Le tri par sélection cherche le minimum parmi les $n$ n éléments ( $n - 1$ n-1 comparaisons), le place en tête, puis recommence sur les $n - 1$ n-1 restants ( $n - 2$ n-2 comparaisons), etc. Total : $(n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2}$ (n-1)+(n-2)+…+1=(n(n-1))/2.
Pour $n = 1 0^{6}$ n=10⁶ : environ $5 \times 1 0^{11}$ 5×10¹¹ comparaisons. À $1 0^{9}$ 10⁹ opérations par seconde, environ 500 secondes, plus de 8 minutes. Doubler $n$ n multiplie le temps par 4 : c'est un coût quadratique.
Le tri fusion coupe la liste en deux, trie chaque moitié, puis les fusionne en au plus $n$ n comparaisons. Il y a $lo g_{2} n$ log₂ n niveaux de découpage, chacun coûtant au plus $n$ n : environ $n lo g_{2} n$ nlog₂ n. Pour $n = 1 0^{6}$ n=10⁶, $lo g_{2} n \approx 20$ log₂ n≈20, soit $2 \times 1 0^{7}$ 2×10⁷ comparaisons, environ $0, 02$ 0,02 seconde. Le rapport $\frac{n ^{2} /2}{n l o g _{2} n} = \frac{n}{2 l o g _{2} n}$ (n²/2)/(nlog₂ n)=n/2log₂n vaut environ 25 000.
3. NSI : mesurer et choisir
3 min
On vérifie expérimentalement en Python avec le module time : on mesure les deux tris pour $n = 1000$ n=1 000, $2000$ 2 000, $4000$ 4 000. Le temps du tri par sélection est multiplié par environ 4 à chaque doublement, celui du tri fusion par un peu plus de 2.
Pour de petites listes, le tri quadratique peut suffire, et le tri par insertion est même très rapide sur une liste presque triée. La fonction sorted de Python utilise Timsort, un mélange de tri fusion et de tri par insertion, qui exploite ces deux avantages.
4. Conclusion
1,5 min
L'écart entre dix minutes et un centième de seconde vient de la forme du coût : $\frac{n ^{2}}{2}$ n²/2 contre $n lo g_{2} n$ nlog₂n. Pour de grandes données, choisir le bon algorithme compte plus que d'avoir une machine rapide. J'ouvre sur la question de savoir si l'on peut trier plus vite que $n lo g_{2} n$ nlog₂ n.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

(n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2} \approx 5 \times 1 0^{11} pour n = 1 0^{6} (n-1)+(n-2)+\dots+1=(n(n-1))/2\approx5\times10¹¹ pour n=10⁶ n lo g_{2} n \approx 1 0^{6} \times 20 = 2 \times 1 0^{7} \frac{5 \times 1 0 ^{11}}{1 0 ^{9}} = 500 s contre 0, 02 s nlog₂n\approx10⁶\times20=2\times10⁷ 5\times10¹¹/10⁹=500 s contre 0,02 s

Conclusion : la réponse à la question

Le coût d'un algorithme se calcule par une somme, et sa croissance décide de son utilité. Un tri quadratique devient inutilisable sur un million de données, un tri en $n lo g n$ nlog n reste instantané.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Démontrez que 1 + 2 + … + (n − 1) = n(n − 1)/2.

On écrit la somme dans les deux sens et on ajoute terme à terme : n − 1 couples de somme n.

Si un tri quadratique trie 10 000 nombres en 0,1 s, combien de temps pour 100 000 ?

Le nombre de données est multiplié par 10, le temps par 100 : environ 10 s.

Pourquoi log₂ n niveaux dans le tri fusion ?

On divise par 2 jusqu'à obtenir des listes de taille 1 : il faut $k$ k étapes avec $2^{k} = n$ 2^(k)=n.

Le tri par insertion est-il toujours quadratique ?

Dans le pire cas oui ; sur une liste déjà triée, il ne fait que n − 1 comparaisons.

Que signifie la notation O(n²) ?

Le nombre d'opérations est majoré par $C n^{2}$ Cn² pour une constante $C$ C, à partir d'un certain rang.

Les pièges qui coûtent des points

Confondre nombre d'opérations et temps exact : on raisonne en ordre de grandeur.
Croire qu'une machine 10 fois plus rapide compense un algorithme quadratique.
Oublier le facteur 1/2 dans n(n − 1)/2.

Revoir les notions

Autres questions : algorithmes et complexité

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →