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

Introduction à la 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 fonction de la taille de ses données d'entrée ( $n$ ).

Complexité temporelle : Mesure le nombre d'opérations élémentaires effectuées.
Notation Grand O : On s'intéresse au comportement asymptotique (quand $n$ devient très grand). On néglige les constantes et les termes de plus bas degré.
Ordres de grandeur classiques :
- $O(1)$ : Temps constant.
- $O(n)$ : Temps linéaire (parcours simple).
- $O(n^2)$ : Temps quadratique (boucles imbriquées).

Méthodes à maîtriser

Compter les opérations : Identifier les boucles. Une boucle simple de $1$ à $n$ donne $O(n)$ . Deux boucles imbriquées donnent $O(n^2)$ .
Identifier le pire cas : Analyser la situation où l'algorithme effectue le maximum d'opérations.
Simplifier l'expression : Garder uniquement le terme dominant (ex: $3n^2 + 5n + 2$ devient $O(n^2)$ ).

Exemples corrigés

Exemple 1 : for i in range(n): print(i) $\rightarrow$ $O(n)$ .
Exemple 2 : for i in range(n): for j in range(n): pass $\rightarrow$ $O(n^2)$ .
Exemple 3 : x = a + b $\rightarrow$ $O(1)$ .

Erreurs fréquentes

Confondre le temps réel (secondes) avec la complexité (nombre d'opérations).
Oublier que les opérations constantes à l'intérieur d'une boucle ne changent pas la complexité globale.
Croire que $O(2n)$ est différent de $O(n)$ : en notation Grand O, les constantes multiplicatives sont ignorées.

L'essentiel du cours

La complexité algorithmique permet d'évaluer l'efficacité d'un algorithme en fonction de la taille de ses données d'entrée ($n$).

Complexité temporelle : Mesure le nombre d'opérations élémentaires effectuées.
Notation Grand O : On s'intéresse au comportement asymptotique (quand $n$ devient très grand). On néglige les constantes et les termes de plus bas degré.
Ordres de grandeur classiques :
- $O(1)$ : Temps constant.
- $O(n)$ : Temps linéaire (parcours simple).
- $O(n^2)$ : Temps quadratique (boucles imbriquées).

Méthodes à maîtriser

Compter les opérations : Identifier les boucles. Une boucle simple de $1$ à $n$ donne $O(n)$. Deux boucles imbriquées donnent $O(n^2)$.
Identifier le pire cas : Analyser la situation où l'algorithme effectue le maximum d'opérations.
Simplifier l'expression : Garder uniquement le terme dominant (ex: $3n^2 + 5n + 2$ devient $O(n^2)$).

Exemples corrigés

Exemple 1 : for i in range(n): print(i) $\rightarrow$ $O(n)$.
Exemple 2 : for i in range(n): for j in range(n): pass $\rightarrow$ $O(n^2)$.
Exemple 3 : x = a + b $\rightarrow$ $O(1)$.

Erreurs fréquentes

Confondre le temps réel (secondes) avec la complexité (nombre d'opérations).
Oublier que les opérations constantes à l'intérieur d'une boucle ne changent pas la complexité globale.
Croire que $O(2n)$ est différent de $O(n)$ : en notation Grand O, les constantes multiplicatives sont ignorées.

🌉 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

🎯 Introduction à la complexité algorithmique

1/4

Quelle est la complexité d'une boucle simple for i in range(n) ?

❓ Questions fréquentes

Est-ce que la recherche dans une liste est toujours O(n) ?

Si la liste n'est pas triée, oui, il faut parcourir tous les éléments au pire cas. Si elle est triée (recherche dichotomique), c'est $O(\log n)$ (à vérifier par le professeur si au programme).

💡 À retenir : La structure des données influence la complexité.

Si la liste n'est pas triée, oui, il faut parcourir tous les éléments au pire cas. Si elle est triée (recherche dichotomique), c'est $O(\log n)$ (à vérifier par le professeur si au programme).

💡 À retenir : La structure des données influence la complexité.

Est-ce que l'initialisation d'une variable est O(n) ?

Non, l'initialisation d'une variable simple (x = 0) est une opération constante, donc $O(1)$ .

💡 À retenir : Une seule instruction = $O(1)$ .

Non, l'initialisation d'une variable simple (x = 0) est une opération constante, donc $O(1)$.

💡 À retenir : Une seule instruction = $O(1)$.

Pourquoi on dit que O(n^2 + n) est O(n^2) ?

Parce que quand $n$ devient très grand (ex: $n = 1000$ ), $n^2$ est beaucoup plus grand que $n$ . Le terme $n$ devient négligeable.

💡 À retenir : On garde toujours le terme de plus haut degré.

Parce que quand $n$ devient très grand (ex: $n = 1000$), $n^2$ est beaucoup plus grand que $n$. Le terme $n$ devient négligeable.

💡 À retenir : On garde toujours le terme de plus haut degré.

Pourquoi on utilise la notation Grand O au lieu du temps en secondes ?

Le temps en secondes dépend de la puissance de la machine (processeur, RAM). La notation Grand O est indépendante du matériel : elle décrit comment le temps d'exécution évolue mathématiquement quand la taille des données ( $n$ ) augmente.

💡 À retenir : Le Grand O mesure la scalabilité de l'algorithme.

Kifach n3raf wach l'algorithme dyali O(n) awla O(n²)?

Chouf ch7al dyal les boucles 3ndek.
Ila 3ndek boucle wa7da li katmchi mn 1 l $n$ , raha $O(n)$ .
Ila 3ndek boucle dakhla f boucle (imbriquée) w jojhom kayt7arko b $n$ , raha $O(n \times n) = O(n^2)$ .

💡 À retenir : Boucles imbriquées = multiplication des complexités.

Chouf ch7al dyal les boucles 3ndek.
Ila 3ndek boucle wa7da li katmchi mn 1 l $n$, raha $O(n)$.
Ila 3ndek boucle dakhla f boucle (imbriquée) w jojhom kayt7arko b $n$, raha $O(n \times n) = O(n^2)$.

💡 À retenir : Boucles imbriquées = multiplication des complexités.

Est-ce que les instructions if changent la complexité ?

Non, le if est une opération de comparaison ( $O(1)$ ). Cependant, si le if est à l'intérieur d'une boucle, il est exécuté $n$ fois, mais il ne change pas l'ordre de grandeur de la boucle elle-même.

💡 À retenir : La complexité est dominée par les boucles, pas par les conditions.

Non, le if est une opération de comparaison ($O(1)$). Cependant, si le if est à l'intérieur d'une boucle, il est exécuté $n$ fois, mais il ne change pas l'ordre de grandeur de la boucle elle-même.

💡 À retenir : La complexité est dominée par les boucles, pas par les conditions.

Chno hiya l'opération élémentaire li khassni n7seb?

C'est l'opération la plus répétée dans ton code : une affectation, une comparaison dans un if, ou une opération arithmétique. On compte combien de fois cette opération est exécutée par rapport à $n$ .

💡 À retenir : Identifie la boucle la plus profonde.

Si j'ai deux boucles successives, c'est O(n^2) ?

Non, c'est $O(n + n) = O(2n)$ , ce qui se simplifie en $O(n)$ . On additionne les complexités des blocs successifs.

💡 À retenir : Séquence = Addition ; Imbrication = Multiplication.

Non, c'est $O(n + n) = O(2n)$, ce qui se simplifie en $O(n)$. On additionne les complexités des blocs successifs.

💡 À retenir : Séquence = Addition ; Imbrication = Multiplication.

Kifach n7seb complexité dyal l'algorithme dyal l'insertion?

L'algorithme d'insertion (tri par insertion) utilise une boucle pour parcourir la liste et une autre boucle pour décaler les éléments. Dans le pire des cas, chaque élément doit être décalé jusqu'au début, ce qui donne $O(n^2)$ .

💡 À retenir : Le pire cas est souvent la référence pour l'examen.

Est-ce que le print compte dans la complexité ?

Oui, techniquement c'est une opération. Si tu fais un print dans une boucle de taille $n$ , la complexité est $O(n)$ .

💡 À retenir : Toute instruction dans une boucle compte.

Oui, techniquement c'est une opération. Si tu fais un print dans une boucle de taille $n$, la complexité est $O(n)$.

💡 À retenir : Toute instruction dans une boucle compte.

Chno l'farq bin l'algorithme li 3ndou O(n) w wa7d 3ndou O(n²)?

L'algorithme $O(n)$ est beaucoup plus rapide. Si $n = 1000$ , $O(n)$ fait 1000 opérations, alors que $O(n^2)$ en fait 1 000 000. La différence devient énorme quand $n$ grandit.

💡 À retenir : Plus la complexité est basse, plus l'algorithme est performant.

L'algorithme $O(n)$ est beaucoup plus rapide. Si $n = 1000$, $O(n)$ fait 1000 opérations, alors que $O(n^2)$ en fait 1 000 000. La différence devient énorme quand $n$ grandit.

💡 À retenir : Plus la complexité est basse, plus l'algorithme est performant.

Est-ce qu'on peut avoir une complexité O(0) ?

Non, le minimum est $O(1)$ , ce qui signifie que l'algorithme prend un temps constant, peu importe la taille des données.

💡 À retenir : $O(1)$ est la meilleure complexité possible.

Non, le minimum est $O(1)$, ce qui signifie que l'algorithme prend un temps constant, peu importe la taille des données.

💡 À retenir : $O(1)$ est la meilleure complexité possible.

✍️ Exercices type examen national

Exercice 1

Soit l'algorithme suivant en Python :

def calcul(n):
    somme = 0
    for i in range(n):
        for j in range(n):
            somme += 1
    return somme

Déterminer la complexité temporelle de cet algorithme en fonction de $n$ .
Si $n=100$ , combien d'opérations somme += 1 sont effectuées ?

Exercice 1

Soit l'algorithme suivant en Python :

def calcul(n):
    somme = 0
    for i in range(n):
        for j in range(n):
            somme += 1
    return somme

Déterminer la complexité temporelle de cet algorithme en fonction de $n$.
Si $n=100$, combien d'opérations somme += 1 sont effectuées ?

Voir la correction détaillée : inscription gratuite

Exercice 2

Soit l'algorithme suivant :

def test(liste):
    n = len(liste)
    for i in range(n):
        print(liste[i])
    for j in range(n):
        print(j)

Déterminer la complexité de cet algorithme.

Voir la correction détaillée : inscription gratuite

Exercice 3

Soit un algorithme qui effectue $T(n) = 5n^2 + 10n + 500$ opérations.

Quelle est sa complexité en notation Grand O ?
Pourquoi peut-on ignorer les termes $10n$ et $500$ ?

Exercice 3

Soit un algorithme qui effectue $T(n) = 5n^2 + 10n + 500$ opérations.

Quelle est sa complexité en notation Grand O ?
Pourquoi peut-on ignorer les termes $10n$ et $500$ ?

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

Architecture des ordinateurs et systèmes d'exploitation Algorithmique et programmation en Python : Les bases Structures de contrôle : Séquences, conditions et boucles Les fonctions et la modularité Les structures de données : Listes, tuples et dictionnaires Traitement de fichiers Bases de données et langage SQL Algorithmique avancée : Recherche et tri