Prepa Help
Prepa Help › Cours › Informatique, 2e année

Complexité des algorithmes itératifs et récursifs : cours et exercices corrigés de prépa

Coût d'un algorithme, opérations élémentaires, complexité temporelle et spatiale dans le meilleur et le pire cas, notation grand O et ordres de grandeur usuels, coût des opérations de Python, complexité des programmes itératifs et récursifs, équations de récurrence usuelles, vérification par la mesure.

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

La complexité d'un algorithme mesure le nombre d'opérations élémentaires qu'il fait en fonction de la taille de son entrée, sans dépendre de la machine. On l'exprime avec la notation grand O, dans le meilleur et le pire cas, en temps et en mémoire. Le chapitre ouvre l'informatique de deuxième année en MP, PSI et TSI au Maroc : depuis 2019, l'exercice d'ouverture de l'épreuve d'informatique du CNC demande presque chaque année de « déterminer la complexité, avec justification ». Tu y trouves le décompte des boucles for et while, le coût caché des opérations de Python (in, tranches, concaténation), la complexité d'une fonction récursive par une équation de récurrence, la complexité spatiale et la vérification par la mesure, puis des exercices corrigés tirés des sujets du CNC.

Ce que tu sauras faire

Un programme juste peut être inutilisable : il répond en une seconde sur un petit exemple et ne finit pas sur les vraies données. La complexité mesure le coût d'un algorithme indépendamment de la machine, pour comparer deux algorithmes et prévoir ce qui se passera sur une grande entrée. À la fin de ce chapitre, tu dois savoir :

L'essentiel : Poser le problème Extrait gratuit

Un extrait de la fiche « L'essentiel » du chapitre. Les démonstrations sont dans le cours détaillé.

À retenir Définitions
  • Taille de l'entrée nn : longueur d'une liste ou d'une chaîne, valeur d'un entier, dimensions d'une matrice ; plusieurs tailles si besoin (nn et kk), toujours nommées.
  • Opération élémentaire : coût indépendant de nn (affectation, comparaison, opération arithmétique sur des nombres bornés, accès L[i]).
  • Complexité temporelle : nombre d'opérations élémentaires en fonction de nn. Complexité spatiale : mémoire supplémentaire, pile d'appels comprise.
  • Meilleur cas, pire cas : à nn fixé, l'entrée qui coûte le moins, celle qui coûte le plus. Le cas moyen se nomme, il ne se calcule pas au programme.

Une méthode du chapitre Extrait gratuit

Méthode Répondre à une question « Déterminer la complexité, avec justification » en temps limité
Quand l’utiliser

C'est la question type de l'exercice d'ouverture du CNC et de nombreux problèmes : quelques lignes de code, et « déterminer la complexité de la fonction, justifier votre réponse ».

Rappel de cours

La justification est exigée et c'est elle qui rapporte les points : une réponse sans justification ne vaut rien. Le pire cas est sous-entendu quand l'énoncé ne précise pas ; la notation attendue est OO.

Démarche
  1. Lire la fonction et nommer la taille de l'entrée (méthode 1).
  2. Repérer le cas étudié (pire cas par défaut) et l'entrée qui l'atteint (méthode 3).
  3. Compter : tours de boucles (méthodes 5, 6), coûts cachés (méthode 7), ou équation de récurrence (méthode 8).
  4. Conclure par un OO simplifié (méthode 4).
  5. Rédiger en deux ou trois phrases : définition de nn, décompte, conclusion.
Rédaction type

« Notons nn = len(L). Dans le pire cas (aucune sortie anticipée, la boucle va jusqu'au bout), la boucle fait n−1n - 1 tours, chacun avec une comparaison : la complexité est en O(n)O(n). »

Exemple traité
def est_croissante(L):
    # L : liste de nombres ; renvoie True si L est
    # triée dans l'ordre croissant, False sinon
    for i in range(len(L) - 1):
        if L[i] > L[i + 1]:
            return False
    return True

Réponse rédigée : « Notons nn = len(L). Chaque tour fait une comparaison, en temps constant. Dans le pire cas (liste croissante, par exemple [1, 3, 3, 8]), la boucle fait n−1n - 1 tours : la complexité est en O(n)O(n). Dans le meilleur cas (L[0] > L[1]), un seul tour : O(1)O(1). »

Erreurs fréquentes
  • Donner le résultat sans justification.
  • Oublier de définir nn.
  • Recopier la complexité d'une fonction ressemblante sans compter.
Pour s’entraîner

Exercices 2, 3, 4, 5, 6, 14, 15, 16 et 17, problèmes 1, 2 et 3.

Un exercice corrigé Extrait gratuit

Exercice Deux complexités d'ouverture ★☆☆

Aux questions 1 et 3 du sujet, on a écrit les deux fonctions suivantes (la fonction somme(n) de ce sujet n'a rien à voir avec la fonction somme(L) du cours).

def somme(n):
    # n : entier, n >= 1 ; renvoie 1 + 2 + ... + n
    s = 0
    for i in range(1, n + 1):
        s = s + i
    return s

def terme(k):
    # k : entier, k >= 1 ; renvoie k / (1 + 2 + ... + k)
    return k / somme(k)

print(somme(4), terme(4))

Le programme affiche :

10 0.4

Q.2. Déterminer la complexité de la fonction somme(n).

Q.4. Déterminer la complexité de la fonction terme(k).

Indications
  • Méthode 1 : ici la taille de l'entrée est la valeur de l'entier, nn pour la première fonction, kk pour la seconde.
  • Méthode 7 : terme(k) ne contient pas de boucle, mais elle appelle une fonction qui en contient une.
Correction détaillée

Q.2. Analyse. La boucle for i in range(1, n + 1) fait nn tours ; chaque tour fait une addition et une affectation, en temps constant.

La fonction somme(n) fait nn tours de boucle de coût constant, plus l'initialisation et le return : sa complexité est en O(n)O(n), linéaire en la valeur de nn.

Q.4. Analyse. Une fonction sans boucle n'est pas forcément en temps constant : on regarde ce qu'elle appelle.

terme(k) fait un appel somme(k), de coût O(k)O(k), puis une division, en temps constant. Sa complexité est en O(k)O(k).

Interprétation : ces deux fonctions ne sont pas les meilleures possibles. La formule 1+2+⋯+n=n(n+1)21 + 2 + \dots + n = \frac{n(n+1)}{2} donne la même valeur en un nombre constant d'opérations ; c'est le premier exemple du cours (section 1.1).

Méthodes à retenir

Au CNC, la première question de complexité porte souvent sur une fonction de l'exercice d'ouverture : on nomme le paramètre, on compte les tours, on n'oublie pas le coût des fonctions appelées. Voir les méthodes 1, 5 et 17.

Dans le chapitre complet

Le cours détaillé, toute la fiche « L'essentiel », 17 méthodes, 20 pièges corrigés, la carte mentale, 32 exercices corrigés, 3 problèmes de concours, les fiches à mémoriser et l'assistant qui répond à tes questions. Ce chapitre est offert : il s’ouvre en entier avec un compte d’essai gratuit.

Ouvrir l'essai gratuit

Plan du cours

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

  1. Identifier la taille de l'entrée et les paramètres de la complexité
  2. Choisir l'opération élémentaire et dresser le tableau des coûts
  3. Trouver et écrire une entrée de meilleur cas et une entrée de pire cas
  4. Simplifier en O
  5. Compter les tours de boucles for
  6. Compter les tours d'une boucle while
  7. Tenir compte du coût caché des opérations de Python et des fonctions appelées
  8. Écrire l'équation de récurrence d'une fonction récursive
  9. Résoudre une récurrence par dépliage ou comme suite arithmético-géométrique
  10. Résoudre une récurrence qui divise par 2
  11. Estimer un coût récursif par l'arbre des appels
  12. Repérer et supprimer le coût caché des tranches et des copies dans une fonction récursive
  13. Calculer la complexité spatiale, au meilleur et au pire cas
  14. Comparer deux versions et améliorer un programme
  15. Écrire un programme de complexité imposée et justifier qu'il la respecte
  16. Vérifier une complexité par la mesure et par un compteur
  17. Répondre à une question « Déterminer la complexité, avec justification » en temps limité

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (13)

Entraînement (14)

Approfondissement (5)

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

Questions fréquentes

Comment calculer la complexité d'un algorithme ?

On nomme d'abord la taille de l'entrée, nn (longueur d'une liste, valeur d'un entier, ou plusieurs paramètres). On choisit le cas étudié, souvent le pire. On compte les opérations élémentaires : une boucle de nn tours dont chaque tour coûte O(1)O(1) coûte O(n)O(n), deux boucles imbriquées dépendantes font n(n−1)2\frac{n(n-1)}{2} tours, une variable divisée par 2 donne ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 tours. On conclut par un OO simplifié et une phrase de justification : sans justification, la réponse ne rapporte rien.

Que veut dire la notation grand O ?

f(n)=O(g(n))f(n) = O(g(n)) signifie qu'il existe une constante c>0c > 0 et un rang n0n_0 tels que f(n)≤c g(n)f(n) \leq c\,g(n) pour tout n≥n0n \geq n_0 : ff croît au plus comme gg, à une constante près. On garde le terme dominant et on oublie les constantes : 5n+3=O(n)5n + 3 = O(n), 3n2+100n+7=O(n2)3n^2 + 100n + 7 = O(n^2). La base du logarithme ne compte pas, mais celle d'une exponentielle compte : 4n4^n n'est pas un O(2n)O(2^n).

Quelle différence entre meilleur cas et pire cas ?

On fixe la taille nn, puis on cherche l'entrée de cette taille qui coûte le moins (meilleur cas) et celle qui coûte le plus (pire cas). Pour la recherche séquentielle d'un élément dans une liste, le meilleur cas est l'élément en tête, O(1)O(1), et le pire cas l'élément absent, O(n)O(n). Le meilleur cas n'est jamais « nn petit ».

Comment calculer la complexité d'une fonction récursive ?

On écrit une équation de récurrence : le coût d'un appel hors appels récursifs, plus le coût des appels, avec la valeur au cas de base. C(n)=C(n−1)+aC(n) = C(n - 1) + a donne O(n)O(n), comme la factorielle ; C(n)=C(n/2)+aC(n) = C(n/2) + a donne O(log⁡n)O(\log n), comme la dichotomie ou la puissance rapide ; C(n)=2C(n/2)+anC(n) = 2C(n/2) + an donne O(nlog⁡n)O(n \log n), comme le tri par fusion ; C(n)=2C(n−1)+aC(n) = 2C(n - 1) + a donne O(2n)O(2^n), comme les tours de Hanoï. Pour une récurrence qui divise par 2, on suppose n=2kn = 2^k.

Quelle est la complexité de x in L, append et des tranches en Python ?

Sur une liste de longueur nn : L.append(x), L[i] et len(L) coûtent O(1)O(1) ; x in L, min(L), L.pop(0) et L = L + [x] coûtent O(n)O(n) ; la tranche L[i:j] est une copie et coûte O(j−i)O(j - i). Sur un dictionnaire, k in d coûte O(1)O(1) en moyenne. Une boucle qui contient x in L est donc souvent quadratique, et une fonction récursive qui s'appelle sur L[1:len(L)] coûte O(n2)O(n^2) au lieu de O(n)O(n).

Quelle est la complexité de la dichotomie ?

Sur une liste triée de longueur nn, la recherche dichotomique fait au plus ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1 tours, soit 10 tours pour 1000 éléments et 20 pour un million : O(log⁡n)O(\log n) dans le pire cas, O(1)O(1) dans le meilleur cas (élément trouvé au premier milieu). Écrite avec des tranches au lieu d'indices, elle recopie la moitié de la liste à chaque appel et devient O(n)O(n).

Comment y accéder

Ce chapitre fait partie des chapitres offerts : il s'ouvre en entier avec un compte d'essai gratuit. Créer un compte d'essai ou se connecter. Pour l'accès complet, les tarifs ou une question, écris-nous sur WhatsApp.

Toute ta prépa au même endroit

Pour chaque chapitre : le cours, l'essentiel, les méthodes, les pièges, les exercices corrigés, les problèmes de concours, et un assistant qui répond à tes questions. Programmes du Maroc et de France.

Essayer gratuitement Prepa Help