Boucles imbriquées et complexité en 1ère
Boucles imbriquées et complexité, c'est une notion de mathématiques du chapitre « Algorithmique et programmation Python », au programme de 1ère. Voici le cours, un exemple et de quoi t'entraîner.
Boucles imbriquées et complexité : le cours
Les boucles imbriquées sont des boucles dans des boucles. Elles permettent de traiter des structures complexes, mais elles ralentissent le programme. La complexité mesure combien d'opérations le programme fait : avec deux boucles imbriquées de n éléments, on fait environ $n^2$ opérations.
Exemple
Pour vérifier tous les matchs possibles entre 10 joueurs de tennis, tu dois comparer chaque joueur avec chaque autre : 10 × 10 = 100 comparaisons. C'est une complexité quadratique.
À retenir
Deux boucles imbriquées donnent une complexité en $O(n^2)$ : c'est lent pour les grandes listes.
S'entraîner sur boucles imbriquées et complexité
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
Écris une fonction recherche_dichotomie(liste, cible) qui cherche cible dans une liste triée et retourne son index (ou -1 si absent). Teste avec assert recherche_dichotomie([1, 3, 5, 7, 9], 5) == 2.
Corrige cet exercice avec le tuteur →Exercice 2
Écris une fonction tri_insertion(liste) qui trie une liste en place par insertion. Teste avec assert tri_insertion([3, 1, 4, 1, 5]) == [1, 1, 3, 4, 5].
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique et programmation Python (Mathématiques 1ère).