Informatique · Classes prépa (CPGE) — 2ème année — TSI

Complexité des algorithmes

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é mesure l'efficacité d'un algorithme. On distingue :

Complexité temporelle : Nombre d'opérations élémentaires en fonction de la taille $n$ des données.
Complexité spatiale : Quantité de mémoire auxiliaire nécessaire.
Notation $O(f(n))$ : Définit une borne supérieure de la croissance du temps d'exécution. Les classes de complexité usuelles sont : $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$ .

Méthodes à maîtriser

Comptage des boucles : Une boucle simple de $1$ à $n$ donne $O(n)$ . Deux boucles imbriquées donnent $O(n^2)$ .
Division successive : Si on divise la taille du problème par 2 à chaque étape (ex: recherche dichotomique), on obtient $O(\log n)$ .
Analyse du pire cas : Toujours considérer la situation où l'algorithme effectue le maximum d'opérations.

Exemples corrigés

Somme d'une liste : for x in L: s += x est $O(n)$ .
Recherche dichotomique : Diviser l'espace de recherche par 2 à chaque itération est $O(\log n)$ .
Tri à bulles : Deux boucles imbriquées parcourant $n$ éléments est $O(n^2)$ .

Erreurs fréquentes

Confondre le nombre d'itérations avec la complexité réelle (ex: oublier les opérations internes).
Négliger les constantes : $O(2n)$ est équivalent à $O(n)$ .
Croire que le meilleur cas est la norme pour l'analyse de complexité.

L'essentiel du cours

La complexité mesure l'efficacité d'un algorithme. On distingue :

Complexité temporelle : Nombre d'opérations élémentaires en fonction de la taille $n$ des données.
Complexité spatiale : Quantité de mémoire auxiliaire nécessaire.
Notation $O(f(n))$ : Définit une borne supérieure de la croissance du temps d'exécution. Les classes de complexité usuelles sont : $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$.

Méthodes à maîtriser

Comptage des boucles : Une boucle simple de $1$ à $n$ donne $O(n)$. Deux boucles imbriquées donnent $O(n^2)$.
Division successive : Si on divise la taille du problème par 2 à chaque étape (ex: recherche dichotomique), on obtient $O(\log n)$.
Analyse du pire cas : Toujours considérer la situation où l'algorithme effectue le maximum d'opérations.

Exemples corrigés

Somme d'une liste : for x in L: s += x est $O(n)$.
Recherche dichotomique : Diviser l'espace de recherche par 2 à chaque itération est $O(\log n)$.
Tri à bulles : Deux boucles imbriquées parcourant $n$ éléments est $O(n^2)$.

Erreurs fréquentes

Confondre le nombre d'itérations avec la complexité réelle (ex: oublier les opérations internes).
Négliger les constantes : $O(2n)$ est équivalent à $O(n)$.
Croire que le meilleur cas est la norme pour l'analyse de complexité.

🌉 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é des algorithmes

1/4

Quelle est la complexité d'une boucle for simple parcourant $n$ éléments ?

❓ Questions fréquentes

Pourquoi on utilise O et pas le temps en secondes ?

Le temps en secondes dépend de la machine (processeur, RAM) et du langage. La notation $O$ est une mesure théorique indépendante du matériel, qui décrit comment l'algorithme se comporte quand $n$ devient très grand.

💡 À retenir : $O$ mesure la croissance, pas la durée réelle.

Kifach n7seb complexité dyal boucle li fiha range(0, n, 2) ?

La boucle s'exécute $n/2$ fois.
En notation $O$ , on ignore les constantes multiplicatives ( $1/2$ ).
Donc, $O(n/2)$ devient $O(n)$ .

💡 À retenir : Les constantes multiplicatives sont toujours ignorées dans $O$ .

La boucle s'exécute $n/2$ fois.
En notation $O$, on ignore les constantes multiplicatives ($1/2$).
Donc, $O(n/2)$ devient $O(n)$.

💡 À retenir : Les constantes multiplicatives sont toujours ignorées dans $O$.

Est-ce que la complexité spatiale est toujours égale à la temporelle ?

Non. Un algorithme peut être très rapide ( $O(n)$ ) mais utiliser beaucoup de mémoire ( $O(n)$ pour stocker une copie), ou très lent ( $O(n^2)$ ) mais utiliser très peu de mémoire ( $O(1)$ ).

💡 À retenir : Temps et espace sont deux ressources distinctes.

Non. Un algorithme peut être très rapide ($O(n)$) mais utiliser beaucoup de mémoire ($O(n)$ pour stocker une copie), ou très lent ($O(n^2)$) mais utiliser très peu de mémoire ($O(1)$).

💡 À retenir : Temps et espace sont deux ressources distinctes.

Chno hiya l'far9 bin O(n) et O(n^2) ?

$O(n)$ signifie que si tu doubles la taille des données, le temps double. $O(n^2)$ signifie que si tu doubles la taille, le temps est multiplié par 4 ( $2^2$ ).

💡 À retenir : $O(n^2)$ devient très lent dès que $n$ est grand.

$O(n)$ signifie que si tu doubles la taille des données, le temps double. $O(n^2)$ signifie que si tu doubles la taille, le temps est multiplié par 4 ($2^2$).

💡 À retenir : $O(n^2)$ devient très lent dès que $n$ est grand.

Comment analyser une fonction récursive ?

On utilise une relation de récurrence. Par exemple, si une fonction appelle deux fois la moitié de ses données, on a $T(n) = 2T(n/2) + O(1)$ , ce qui donne $O(n)$ .

💡 À retenir : Utiliser l'arbre des appels pour visualiser la complexité.

On utilise une relation de récurrence. Par exemple, si une fonction appelle deux fois la moitié de ses données, on a $T(n) = 2T(n/2) + O(1)$, ce qui donne $O(n)$.

💡 À retenir : Utiliser l'arbre des appels pour visualiser la complexité.

Est-ce que print() est une opération élémentaire ?

Oui, dans l'analyse de complexité standard, on considère les instructions simples (affectation, comparaison, impression) comme $O(1)$ .

💡 À retenir : Sauf si l'objet à imprimer est de taille $n$ .

Oui, dans l'analyse de complexité standard, on considère les instructions simples (affectation, comparaison, impression) comme $O(1)$.

💡 À retenir : Sauf si l'objet à imprimer est de taille $n$.

Kifach n3ref wach l'algo dyali efficient ?

Compare sa complexité avec les standards : $O(n)$ ou $O(n \log n)$ sont excellents. $O(n^2)$ est acceptable pour $n < 10^4$ . $O(2^n)$ est à éviter absolument.

💡 À retenir : Vise toujours la complexité la plus basse possible.

Compare sa complexité avec les standards : $O(n)$ ou $O(n \log n)$ sont excellents. $O(n^2)$ est acceptable pour $n < 10^4$. $O(2^n)$ est à éviter absolument.

💡 À retenir : Vise toujours la complexité la plus basse possible.

Pourquoi on dit que la recherche dichotomique est O(log n) ?

Parce qu'à chaque étape, on élimine la moitié des éléments restants. Le nombre d'étapes nécessaires pour atteindre 1 élément est le nombre de fois qu'on peut diviser $n$ par 2, soit $\log_2(n)$ .

💡 À retenir : Division = Logarithme.

Est-ce que le pire cas est toujours le cas moyen ?

Non. Le pire cas est le scénario le plus défavorable possible. Le cas moyen est la moyenne sur toutes les entrées possibles. Le pire cas est celui qu'on retient pour garantir la performance.

💡 À retenir : Le pire cas est la garantie de performance.

Si j'ai trois boucles imbriquées, c'est O(n^3) ?

Oui, si chaque boucle parcourt $n$ éléments. Si la première boucle va de $1$ à $n$ , la deuxième de $1$ à $i$ , etc., la complexité peut être différente (ex: $O(n^2)$ ).

💡 À retenir : Toujours vérifier les bornes des boucles.

Oui, si chaque boucle parcourt $n$ éléments. Si la première boucle va de $1$ à $n$, la deuxième de $1$ à $i$, etc., la complexité peut être différente (ex: $O(n^2)$).

💡 À retenir : Toujours vérifier les bornes des boucles.

Est-ce que O(n + log n) est égal à O(n) ?

Oui. En notation $O$ , on ne garde que le terme dominant. Quand $n$ tend vers l'infini, $n$ croît beaucoup plus vite que $\log n$ .

💡 À retenir : Garder uniquement le terme le plus fort.

Oui. En notation $O$, on ne garde que le terme dominant. Quand $n$ tend vers l'infini, $n$ croît beaucoup plus vite que $\log n$.

💡 À retenir : Garder uniquement le terme le plus fort.

Est-ce que l'ordre des instructions change la complexité ?

Non, tant que les instructions sont en séquence. La complexité est déterminée par la structure de contrôle la plus coûteuse (boucles, récursion).

💡 À retenir : La complexité est dominée par la structure la plus lourde.

✍️ Exercices type examen national

Exercice 1

Soit l'algorithme suivant :

def algo(n):
    res = 0
    for i in range(n):
        for j in range(n):
            res += 1
    for k in range(n):
        print(k)
    return res

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

Exercice 1

Soit l'algorithme suivant :

def algo(n):
    res = 0
    for i in range(n):
        for j in range(n):
            res += 1
    for k in range(n):
        print(k)
    return res

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

Voir la correction détaillée : inscription gratuite

Exercice 2

Analyser la complexité de l'algorithme de recherche séquentielle dans une liste de taille $n$ .

def recherche(L, cible):
    for i in range(len(L)):
        if L[i] == cible:
            return i
    return -1

Exercice 2

Analyser la complexité de l'algorithme de recherche séquentielle dans une liste de taille $n$.

def recherche(L, cible):
    for i in range(len(L)):
        if L[i] == cible:
            return i
    return -1

Voir la correction détaillée : inscription gratuite

Exercice 3

Soit une fonction récursive :

def f(n):
    if n <= 1: return 1
    return f(n-1) + f(n-1)

Déterminer la complexité temporelle.

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

Révision et approfondissement du langage Python Structures de données : Listes, Piles et Files Structures de données : Arbres binaires et Arbres binaires de recherche Algorithmes de tri et de recherche Graphes : Représentation et parcours (BFS, DFS)Programmation dynamique Bases de données relationnelles et langage SQL Architecture des ordinateurs et systèmes d'exploitation