Informatique · Classes prépa (CPGE) — 1ère année — ECS

Complexité algorithmique

Le cours expliqué simplement, les questions que tous les élèves se posent et des exercices type examen national. Programme marocain, gratuit.

📘 Fiche de cours

L'essentiel du cours

La complexité algorithmique permet d'évaluer l'efficacité d'un algorithme en termes de temps (temporelle) et d'espace (spatiale). On utilise la notation de Landau, notée $O(f(n))$ , où $n$ est la taille des données en entrée.

$O(1)$ : Temps constant (accès direct).
$O(\log n)$ : Temps logarithmique (recherche dichotomique).
$O(n)$ : Temps linéaire (parcours d'une liste).
$O(n^2)$ : Temps quadratique (boucles imbriquées).

Méthodes à maîtriser

Compter les opérations : Identifier les boucles et les instructions élémentaires.
Identifier le pire cas : Analyser la situation où l'algorithme effectue le maximum d'opérations.
Simplifier : Garder uniquement le terme dominant et ignorer les constantes multiplicatives (ex: $O(3n + 5) = O(n)$ ).

Exemples corrigés

Exemple 1 : Une boucle simple for i in range(n): print(i) est en $O(n)$ . Exemple 2 : Deux boucles imbriquées for i in range(n): for j in range(n): ... est en $O(n^2)$ .

Erreurs fréquentes

Confondre le nombre d'opérations exact avec l'ordre de grandeur (Grand O).
Oublier que les opérations constantes à l'intérieur d'une boucle ne changent pas la complexité globale.
Négliger le cas où $n$ tend vers l'infini.

L'essentiel du cours

$O(1)$ : Temps constant (accès direct).
$O(\log n)$ : Temps logarithmique (recherche dichotomique).
$O(n)$ : Temps linéaire (parcours d'une liste).
$O(n^2)$ : Temps quadratique (boucles imbriquées).

Méthodes à maîtriser

Compter les opérations : Identifier les boucles et les instructions élémentaires.
Identifier le pire cas : Analyser la situation où l'algorithme effectue le maximum d'opérations.
Simplifier : Garder uniquement le terme dominant et ignorer les constantes multiplicatives (ex: $O(3n + 5) = O(n)$).

Exemples corrigés

Exemple 1 : Une boucle simple for i in range(n): print(i) est en $O(n)$. Exemple 2 : Deux boucles imbriquées for i in range(n): for j in range(n): ... est en $O(n^2)$.

Erreurs fréquentes

Confondre le nombre d'opérations exact avec l'ordre de grandeur (Grand O).
Oublier que les opérations constantes à l'intérieur d'une boucle ne changent pas la complexité globale.
Négliger le cas où $n$ tend vers l'infini.

🌉 Jisr : les mots du chapitre FR ⇄ AR

Tu as appris les sciences en arabe ? Touche un mot pour voir sa traduction et une explication en darija.

La question que tu n'oses pas poser en classe ? Pose-la à UstadZéro jugement, même en darija, même à minuit. Il t'explique pas à pas et corrige ta démarche. Gratuit.Commencer gratuitement

Défi flash : 4 questions

Sans compte

🎯 Complexité algorithmique

1/4

Quelle est la complexité d'une boucle simple qui parcourt une liste de taille $n$ ?

❓ Questions fréquentes

C'est quoi la différence entre complexité temporelle et spatiale ?

La complexité temporelle mesure le nombre d'opérations effectuées par l'algorithme en fonction de la taille de l'entrée.
La complexité spatiale mesure la quantité de mémoire vive (RAM) supplémentaire nécessaire pour exécuter l'algorithme.

💡 À retenir : Le temps est souvent la contrainte principale, mais l'espace devient critique pour les très gros volumes de données.

Chno hiya l'utilité dyal notation O(n) f l'examen ?

Elle permet de comparer deux algorithmes sans dépendre de la puissance de la machine.
Elle donne une idée sur le comportement de l'algorithme quand $n$ devient très grand.

💡 À retenir : $O(n)$ nous aide à prédire si un programme va "planter" sur des données massives.

Elle permet de comparer deux algorithmes sans dépendre de la puissance de la machine.
Elle donne une idée sur le comportement de l'algorithme quand $n$ devient très grand.

💡 À retenir : $O(n)$ nous aide à prédire si un programme va "planter" sur des données massives.

Kifach n7seb complexité dyal boucle wa7da f west boucle okhra ?

Tu comptes le nombre d'itérations de la boucle externe ( $n$ fois).
Tu comptes le nombre d'itérations de la boucle interne ( $n$ fois).
Tu multiplies les deux : $n \times n = n^2$ .

💡 À retenir : Des boucles imbriquées multiplient les complexités.

Tu comptes le nombre d'itérations de la boucle externe ($n$ fois).
Tu comptes le nombre d'itérations de la boucle interne ($n$ fois).
Tu multiplies les deux : $n \times n = n^2$.

💡 À retenir : Des boucles imbriquées multiplient les complexités.

Est-ce que l'instruction print() est toujours O(1) ?

Oui, dans le cadre du programme, l'affichage d'une valeur simple est considéré comme une opération élémentaire à temps constant.

💡 À retenir : Toute opération élémentaire (affectation, addition, comparaison) est $O(1)$ .

Oui, dans le cadre du programme, l'affichage d'une valeur simple est considéré comme une opération élémentaire à temps constant.

💡 À retenir : Toute opération élémentaire (affectation, addition, comparaison) est $O(1)$.

Pourquoi on ignore les constantes dans la notation O(n) ?

La notation $O$ s'intéresse à la croissance asymptotique (quand $n \to \infty$ ).
Une constante (comme $2n$ ou $5n$ ) ne change pas la forme de la courbe de croissance.

💡 À retenir : Seul le terme qui croît le plus vite compte.

La notation $O$ s'intéresse à la croissance asymptotique (quand $n \to \infty$).
Une constante (comme $2n$ ou $5n$) ne change pas la forme de la courbe de croissance.

💡 À retenir : Seul le terme qui croît le plus vite compte.

Wach l'ordre dyal l'instruction f l'algorithme kay2atar 3la complexité ?

Si les instructions sont séquentielles, on additionne les complexités.
On garde toujours la plus grande complexité (le terme dominant).

💡 À retenir : $O(n + n^2) = O(n^2)$ .

Si les instructions sont séquentielles, on additionne les complexités.
On garde toujours la plus grande complexité (le terme dominant).

💡 À retenir : $O(n + n^2) = O(n^2)$.

Comment déterminer la complexité d'un algorithme récursif ?

On écrit l'équation de récurrence (ex: $T(n) = T(n-1) + O(1)$ ).
On résout cette équation pour trouver la forme fermée.

💡 À retenir : La récursivité simple est souvent $O(n)$ .

On écrit l'équation de récurrence (ex: $T(n) = T(n-1) + O(1)$).
On résout cette équation pour trouver la forme fermée.

💡 À retenir : La récursivité simple est souvent $O(n)$.

Est-ce que le meilleur cas est utile pour l'examen ?

Oui, mais le programme demande principalement d'analyser le "pire cas" pour garantir que l'algorithme fonctionne toujours dans un temps acceptable.

💡 À retenir : Le pire cas est la borne supérieure de la complexité.

Si j'ai une boucle while qui divise n par 2 à chaque fois, c'est quoi la complexité ?

C'est une complexité logarithmique, notée $O(\log n)$ , car le nombre d'étapes est divisé par 2 à chaque itération.

💡 À retenir : Toute division répétée par une constante donne $O(\log n)$ .

C'est une complexité logarithmique, notée $O(\log n)$, car le nombre d'étapes est divisé par 2 à chaque itération.

💡 À retenir : Toute division répétée par une constante donne $O(\log n)$.

Comment savoir si un algorithme est efficace ?

Il doit avoir une complexité la plus basse possible (ex: $O(n)$ est mieux que $O(n^2)$ ).
Il doit respecter les contraintes de temps de l'énoncé.

💡 À retenir : Moins la complexité est élevée, plus l'algorithme est rapide.

Il doit avoir une complexité la plus basse possible (ex: $O(n)$ est mieux que $O(n^2)$).
Il doit respecter les contraintes de temps de l'énoncé.

💡 À retenir : Moins la complexité est élevée, plus l'algorithme est rapide.

Est-ce que la taille de la liste influence la complexité ?

Oui, la taille de la liste est la variable $n$ qui définit la complexité.

💡 À retenir : La complexité dépend toujours de la taille des données d'entrée.

Oui, la taille de la liste est la variable $n$ qui définit la complexité.

💡 À retenir : La complexité dépend toujours de la taille des données d'entrée.

Pourquoi on utilise n comme variable ?

C'est la convention standard en informatique pour représenter le nombre d'éléments à traiter.

💡 À retenir : $n$ est la taille de l'entrée.

C'est la convention standard en informatique pour représenter le nombre d'éléments à traiter.

💡 À retenir : $n$ est la taille de l'entrée.

✍️ Exercices type examen national

Exercice 1

Soit l'algorithme suivant :

def calcul(L):
    n = len(L)
    somme = 0
    for i in range(n):
        for j in range(i, n):
            somme += L[j]
    return somme

Déterminer la complexité temporelle de cet algorithme en fonction de $n$ .

Exercice 1

Soit l'algorithme suivant :

def calcul(L):
    n = len(L)
    somme = 0
    for i in range(n):
        for j in range(i, n):
            somme += L[j]
    return somme

Déterminer la complexité temporelle de cet algorithme en fonction de $n$.

Voir la correction détaillée : inscription gratuite

Exercice 2

Soit un algorithme qui parcourt une liste de taille $n$ et pour chaque élément, effectue une recherche dichotomique dans une autre liste triée de taille $n$ . Quelle est la complexité totale ?

Exercice 2

Soit un algorithme qui parcourt une liste de taille $n$ et pour chaque élément, effectue une recherche dichotomique dans une autre liste triée de taille $n$. Quelle est la complexité totale ?

Voir la correction détaillée : inscription gratuite

Exercice 3

Analyser la complexité de l'algorithme suivant :

def test(n):
    i = 1
    while i < n:
        i = i * 2

Voir la correction détaillée : inscription gratuite

Un prof de Informatique pour aller plus loin

Les cours du soir avec des profs vérifiés arrivent : inscris-toi pour être prévenu(e) en premier.

Être prévenu(e) gratuitement

Autres chapitres de Informatique

Introduction à l'informatique et architecture des ordinateurs Algorithmique et programmation en Python : Les bases Structures de contrôle : Séquences, conditions et boucles Fonctions et portée des variables Types de données composés : Listes, tuples et chaînes de caractères Dictionnaires et ensembles Manipulation de fichiers Algorithmes de tri et de recherche Récursivité Introduction au calcul scientifique avec NumPy Visualisation de données avec Matplotlib Bases de données relationnelles et langage SQL