Algorithmique · Écoles d'ingénieurs — ENSIAS

Introduction à l'algorithmique et complexité

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 mesure l'efficacité d'un algorithme en fonction de la taille de l'entrée $n$ .

Complexité temporelle : Temps nécessaire pour exécuter l'algorithme.
Complexité spatiale : Mémoire nécessaire pour exécuter l'algorithme.
Notation $O(n)$ : Définit une borne supérieure du temps d'exécution.
Classes classiques : $O(1)$ (constant), $O(\log n)$ (logarithmique), $O(n)$ (linéaire), $O(n \log n)$ (linéarithmique), $O(n^2)$ (quadratique), $O(2^n)$ (exponentiel).

Méthodes à maîtriser

Compter les opérations : Identifier la boucle dominante.
Analyser les boucles : Une boucle simple donne $O(n)$ , deux boucles imbriquées donnent $O(n^2)$ .
Réduction de taille : Si l'entrée est divisée par 2 à chaque étape, on obtient $O(\log n)$ .
Simplification : Garder uniquement le terme de plus haut degré et ignorer les constantes (ex: $3n^2 + 5n + 2 \rightarrow O(n^2)$ ).

Exemples corrigés

Recherche séquentielle : Parcourir un tableau de taille $n$ est $O(n)$ .
Boucles imbriquées :
```
pour i de 1 à n:
  pour j de 1 à n:
    afficher(i, j)
```
Le nombre d'opérations est $n \times n = n^2$ $n \times n = n^{2}$ , donc $O(n^2)$ $O (n^{2})$ .

Erreurs fréquentes

Oublier de considérer le "pire cas" (Worst Case).
Confondre le nombre d'instructions avec la classe de complexité.
Négliger les appels récursifs dans le calcul de la complexité.

L'essentiel du cours

La complexité algorithmique mesure l'efficacité d'un algorithme en fonction de la taille de l'entrée $n$.

Complexité temporelle : Temps nécessaire pour exécuter l'algorithme.
Complexité spatiale : Mémoire nécessaire pour exécuter l'algorithme.
Notation $O(n)$ : Définit une borne supérieure du temps d'exécution.
Classes classiques : $O(1)$ (constant), $O(\log n)$ (logarithmique), $O(n)$ (linéaire), $O(n \log n)$ (linéarithmique), $O(n^2)$ (quadratique), $O(2^n)$ (exponentiel).

Méthodes à maîtriser

Compter les opérations : Identifier la boucle dominante.
Analyser les boucles : Une boucle simple donne $O(n)$, deux boucles imbriquées donnent $O(n^2)$.
Réduction de taille : Si l'entrée est divisée par 2 à chaque étape, on obtient $O(\log n)$.
Simplification : Garder uniquement le terme de plus haut degré et ignorer les constantes (ex: $3n^2 + 5n + 2 \rightarrow O(n^2)$).

Exemples corrigés

Recherche séquentielle : Parcourir un tableau de taille $n$ est $O(n)$.
Boucles imbriquées :
```
pour i de 1 à n:
  pour j de 1 à n:
    afficher(i, j)
```
Le nombre d'opérations est $n \times n = n^2$, donc $O(n^2)$.

Erreurs fréquentes

Oublier de considérer le "pire cas" (Worst Case).
Confondre le nombre d'instructions avec la classe de complexité.
Négliger les appels récursifs dans le calcul de la 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

🎯 Introduction à l'algorithmique et complexité

1/4

Quelle est la complexité d'une boucle simple parcourant un tableau de taille $n$ ?

❓ Questions fréquentes

Qu'est-ce qu'une opération élémentaire ?

C'est une instruction dont le temps d'exécution est considéré comme constant, indépendamment des données. Exemples : affectation, comparaison, addition, accès à un indice de tableau.

💡 À retenir : Une opération élémentaire prend un temps $O(1)$ .

C'est une instruction dont le temps d'exécution est considéré comme constant, indépendamment des données. Exemples : affectation, comparaison, addition, accès à un indice de tableau.

💡 À retenir : Une opération élémentaire prend un temps $O(1)$.

kifach n7seb complexité dyal boucle wa7da?

Chof ch7al mn mara ghatkhdem l-boucle.
Ila kant l-boucle ghatkhdem $n$ mara, l-complexité hiya $O(n)$ .
Ila kant l-boucle ghatkhdem $n/2$ mara, l-complexité hiya $O(n)$ (hit l-constantes makhassnach n7sbohom).

💡 À retenir : L-complexité hiya l-3adad dyal l-marat li ghatkhdem fiha l-instruction li dakhla f l-boucle.

Chof ch7al mn mara ghatkhdem l-boucle.
Ila kant l-boucle ghatkhdem $n$ mara, l-complexité hiya $O(n)$.
Ila kant l-boucle ghatkhdem $n/2$ mara, l-complexité hiya $O(n)$ (hit l-constantes makhassnach n7sbohom).

💡 À retenir : L-complexité hiya l-3adad dyal l-marat li ghatkhdem fiha l-instruction li dakhla f l-boucle.

Pourquoi ignore-t-on les constantes dans la notation O ?

La notation $O$ s'intéresse au comportement asymptotique (quand $n$ tend vers l'infini). Les constantes ne changent pas la vitesse de croissance de la fonction.

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

La notation $O$ s'intéresse au comportement asymptotique (quand $n$ tend vers l'infini). Les constantes ne changent pas la vitesse de croissance de la fonction.

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

chno lfar9 bin O(n) w O(n^2)?

$O(n)$ (linéaire) kayzid lwa9t b nafs l9ima m3a l'input.
$O(n^2)$ (quadratique) kayzid lwa9t b saroukh ila zad l'input (ila tzaad $n$ b 10, lwa9t kaytzaad b 100).

💡 À retenir : $O(n)$ ahsan bzaf mn $O(n^2)$ f l'efficacité.

$O(n)$ (linéaire) kayzid lwa9t b nafs l9ima m3a l'input.
$O(n^2)$ (quadratique) kayzid lwa9t b saroukh ila zad l'input (ila tzaad $n$ b 10, lwa9t kaytzaad b 100).

💡 À retenir : $O(n)$ ahsan bzaf mn $O(n^2)$ f l'efficacité.

Comment calculer la complexité d'un algorithme avec des boucles imbriquées ?

Multiplier le nombre d'itérations de la boucle externe par celui de la boucle interne.
Si la boucle externe fait $n$ et l'interne fait $n$ , la complexité est $n \times n = O(n^2)$ .

💡 À retenir : Pour des boucles imbriquées, on multiplie les complexités de chaque niveau.

Multiplier le nombre d'itérations de la boucle externe par celui de la boucle interne.
Si la boucle externe fait $n$ et l'interne fait $n$, la complexité est $n \times n = O(n^2)$.

💡 À retenir : Pour des boucles imbriquées, on multiplie les complexités de chaque niveau.

kifach n3ref wach l'algo dyali 3ndo complexité logaritmia?

Ila knti kat9sam l-input 3la 2 (aw ay ra9m) f kol étape dyal l-boucle, hna 3ndk complexité $O(\log n)$ .

💡 À retenir : L-logarithme kayban f l-khawarizmiyat li kay9smo l-mochkil 3la 2 (b7al recherche dichotomique).

Ila knti kat9sam l-input 3la 2 (aw ay ra9m) f kol étape dyal l-boucle, hna 3ndk complexité $O(\log n)$.

💡 À retenir : L-logarithme kayban f l-khawarizmiyat li kay9smo l-mochkil 3la 2 (b7al recherche dichotomique).

La complexité spatiale est-elle toujours égale à la complexité temporelle ?

Non. Un algorithme peut utiliser très peu de mémoire ( $O(1)$ ) mais prendre beaucoup de temps ( $O(n^2)$ ), ou inversement.

💡 À retenir : La mémoire dépend des structures de données créées, le temps dépend des opérations effectuées.

Non. Un algorithme peut utiliser très peu de mémoire ($O(1)$) mais prendre beaucoup de temps ($O(n^2)$), ou inversement.

💡 À retenir : La mémoire dépend des structures de données créées, le temps dépend des opérations effectuées.

Qu'est-ce que le "pire cas" (Worst Case) ?

C'est le scénario où l'algorithme effectue le nombre maximal d'opérations pour une entrée de taille $n$ . C'est la mesure standard en examen.

💡 À retenir : On analyse toujours le pire cas pour garantir que l'algorithme ne dépassera jamais ce temps.

C'est le scénario où l'algorithme effectue le nombre maximal d'opérations pour une entrée de taille $n$. C'est la mesure standard en examen.

💡 À retenir : On analyse toujours le pire cas pour garantir que l'algorithme ne dépassera jamais ce temps.

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

Oui. En notation Grand O, on ne garde que le terme dominant (celui qui croît le plus vite quand $n$ devient très grand).

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

Oui. En notation Grand O, on ne garde que le terme dominant (celui qui croît le plus vite quand $n$ devient très grand).

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

Si un algorithme a une complexité O(2^n), est-il efficace ?

Non, c'est une complexité exponentielle. Pour des valeurs de $n$ même petites (ex: $n=50$ ), le temps d'exécution devient gigantesque.

💡 À retenir : Les algorithmes exponentiels sont inutilisables pour de grandes entrées.

Non, c'est une complexité exponentielle. Pour des valeurs de $n$ même petites (ex: $n=50$), le temps d'exécution devient gigantesque.

💡 À retenir : Les algorithmes exponentiels sont inutilisables pour de grandes entrées.

Comment traiter les conditions (if/else) dans l'analyse ?

On prend le pire des cas entre le bloc if et le bloc else.

💡 À retenir : La complexité est déterminée par le chemin le plus long.

La complexité dépend-elle du langage de programmation ?

Non, la complexité est une mesure théorique de l'algorithme lui-même, indépendante du langage ou de la machine.

💡 À retenir : L'analyse de complexité est mathématique.

✍️ Exercices type examen national

Exercice 1

Soit l'algorithme suivant :

Algorithme Calcul(n)
Pour i de 1 à n faire
    Pour j de 1 à i faire
        Afficher(i * j)
    FinPour
FinPour

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

Exercice 1

Soit l'algorithme suivant :

Algorithme Calcul(n)
Pour i de 1 à n faire
    Pour j de 1 à i faire
        Afficher(i * j)
    FinPour
FinPour

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 recherche un élément dans un tableau trié en divisant l'espace de recherche par deux à chaque étape. Quelle est sa complexité ? Justifiez.

Voir la correction détaillée : inscription gratuite

Exercice 3

Analyser la complexité de l'algorithme suivant :

Pour i de 1 à n faire
    x = x + 1
FinPour
Pour j de 1 à n faire
    Pour k de 1 à n faire
        y = y + 1
    FinPour
FinPour

Voir la correction détaillée : inscription gratuite

Un prof de Algorithmique 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 Algorithmique

Structures de données linéaires : Listes, Piles et Files Récursivité et méthodes de conception d'algorithmes Algorithmes de tri et de recherche Arbres binaires et arbres de recherche Structures de données avancées : Tas (Heaps) et Files de priorité Tables de hachage (Hash Tables)Graphes : Représentations et parcours (BFS, DFS)Algorithmes sur les graphes : Plus courts chemins et arbres couvrants Programmation dynamique Algorithmes gloutons Introduction à la théorie de la complexité (P vs NP)