Complexité Algorithmique
Cours Dr. Nesrine MEDDEB
Chapitre 1 :
Introduction à la complexité
1. Qu’est-ce qu’un algorithme ?
Un algorithme est une suite d’instructions permettant
de résoudre un problème
Il doit être clair, précis, fini.
Exemple simple : faire du thé (algorithme de la vie
quotidienne)
Faire chauffer de l’eau.
Mettre un sachet de thé dans une tasse.
Verser l’eau chaude.
Attendre quelques minutes.
Retirer le sachet et boire.
➡Chaque étape est simple et suit un ordre précis.
1. Qu’est-ce qu’un algorithme ?
Notion d'efficacité:
Plusieurs chemins pour une même solution:
Comment choisir ?
Problèmes de grande taille
Plusieurs solutions:
Implémenter et tester les différentes solutions
Prédire le temps/coût nécessaire
1. Qu’est-ce qu’un algorithme ?
Pourquoi se soucier de l’efficacité ?
Mémoire : possibilité de calculer au pas
Temps :
1 min, 1 jour, 1 an de calcul ?
2x plus de donnée = 4x plus de temps ? 16x ?
Consommation électrique
Embarqué
…...
2. Pourquoi mesurer la complexité ?
Deux algorithmes peuvent résoudre le même problème,
mais pas de la même façon.
On veut mesurer l’efficacité (en temps et en mémoire).
Exemple : Recherche d’un numéro dans un annuaire
Méthode 1 (linéaire) : lire chaque page jusqu’à trouver
le numéro.
Si l’annuaire a 1000 pages → on peut lire jusqu’à 1000 pages.
Méthode 2 (dichotomique) : ouvrir au milieu, puis
diviser en deux, etc.
➡Les deux trouvent la solution, mais la seconde est
beaucoup plus efficace.
2. Pourquoi mesurer la complexité ?
On cherche un numéro dans un annuaire de 1000
pages.
Si l’annuaire est trié (comme dans la vraie vie), on peut
utiliser la recherche dichotomique :
Au lieu de feuilleter page par page, on ouvre au milieu.
Puis, on regarde si le numéro cherché est avant ou après.
On divise par 2 la recherche à chaque étape.
2. Pourquoi mesurer la complexité ?
Étapes pour 1000 pages :
On commence avec 1000 pages.
Première ouverture → on regarde page 500.
Il reste 500 pages à chercher.
Deuxième ouverture → on regarde page 250 ou 750.
Il reste 250 pages.
Troisième ouverture → on regarde page 125, 375, etc.
Il reste 125 pages.
Quatrième ouverture → il reste environ 62 pages.
Cinquième ouverture → il reste 31 pages.
Sixième ouverture → il reste 15 pages.
Septième ouverture → il reste 7 pages.
Huitième ouverture → il reste 3 pages.
Neuvième ouverture → il reste 1 ou 2 pages.
Dixième ouverture → on trouve le numéro exact ✅
2. Pourquoi mesurer la complexité ?
2. Pourquoi mesurer la complexité ?
La recherche dichotomique consiste à diviser la zone de
recherche par 2 à chaque étape.
Si on commence avec n éléments, après chaque étape il en
reste n/2, puis n/4, puis n/8, etc.
Donc au bout de k étapes, il reste : éléments à vérifier.
Quand s’arrête la recherche ?
On s’arrête quand il ne reste qu’un seul élément (ou zéro).
Résolution de l’équation
En prenant le logarithme en base 2 :
2. Pourquoi mesurer la complexité ?
Le nombre d’étapes est donné par :
Ici n = 1000.
Donc :
➡Il faut environ 10 ouvertures maximum pour trouver
le numéro.
➡Les deux trouvent la solution, mais la seconde est
beaucoup plus efficace.
3. Qu’est ce que la complexité?
La complexité d’un algorithme consiste en l’étude de la
quantité de ressources (de temps ou d’espace)
nécessaire à l’exécution de cet algorithme.
3. Qu’est ce que la complexité?
3. Qu’est ce que la complexité?
3. Qu’est ce que la complexité?
Différence entre temps et espace
Complexité en temps :
combien d’opérations sont nécessaires ?
Complexité en espace :
combien de mémoire est utilisée ?
Exemple 2 : Copier une liste
Méthode 1 : On recopie les éléments un par un dans une
nouvelle liste → utilise de la mémoire supplémentaire.
Méthode 2 : On travaille directement sur la liste originale →
peu de mémoire, mais risque de modifier les données d’origine.
4. Exemple informatique concret
Prenons un programme en C qui cherche si un nombre
est dans une liste.
Si la liste a n éléments → au
pire, on compare n fois.
Complexité en temps :
O(n).
Complexité en espace :
O(1) (pas de mémoire
supplémentaire).
Symbole complexité
4. Exemple informatique concret
Chaque fois, on divise la liste par 2.
Nombre d’opérations ≈ log₂(n).
Complexité en temps : O(log n).
5. Importance dans la vie réelle
Les moteurs de recherche (Google) doivent trouver une
information en quelques millisecondes malgré des
milliards de pages.
Les banques doivent gérer des millions de transactions
par seconde.
Les réseaux sociaux doivent trier, filtrer, et recommander
du contenu rapidement.
Sans analyse de complexité, un algorithme trop lent peut
devenir inutilisable dès que les données sont massives.
Exercice
fonction somme(liste):
n ← longueur(liste)
total ← 0
pour i de 0 à n-1:
total ← total + liste[i]
retourner total
Exercice
1. Complexité en temps ⏱
La boucle pour i de 0 à n-1 s’exécute exactement n fois.
À chaque itération, l’opération total ← total + liste[i] est
constante (O(1)).
Donc le temps total est O(n)
➡La complexité temporelle est linéaire : O(n).
Exemple
Complexité Nom Interprétation
d’algorithme
Accéder à un élément Toujours la même durée,
O(1) Constante
d’un tableau peu importe (n).
Très efficace, le temps
O(log n) Logarithmique Recherche dichotomique croît lentement même si
(n) augmente beaucoup.
Le temps croît
O(n) Linéaire Recherche séquentielle proportionnellement à la
taille de l’entrée.
Un peu plus que linéaire,
O(n log n) Quasi-linéaire Tri rapide, tri fusion souvent le meilleur
possible pour le tri.
Tri par insertion, tri à Le temps explose vite
O(n²) Quadratique
bulles dès que (n) est grand.
Algorithmes naïfs de
O(n³) Cubique multiplications de Encore plus coûteux.
matrices
Problème du voyageur
Impraticable dès que (n)
O(2^n) Exponentielle de commerce
est grand.
(algorithme naïf)
Catastrophique,
Génération de toutes les
O(n!) Factorielle inutilisable sauf pour de
permutations
très petites tailles.
Principe du tri fusion
1. Diviser : On coupe la liste en deux sous-listes.
2. Régner : On trie récursivement chaque sous-liste avec le même procédé.
3. Fusionner : On rassemble (fusionne) les deux sous-listes triées en une seule
liste triée.
Exemple pas à pas
Imaginons qu’on veuille trier :
38,27,43,3,9,82,10
On divise en deux :
38,27,43 et 3,9,82,10
On redécoupe chaque partie :
38, et 27,43 et 3,9 et 82,10
On trie les plus petites parties et on fusionne :
27,43 → triée
3,9 → triée
10,82 → triée
Fusion finale :
3,9,10,27,38,43,82 ✅
Complexité cubique
Si on veut multiplier deux matrices A et B de taille n×m,
la méthode classique est :
Il y a 3 boucles imbriquées :
une pour parcourir les lignes de A,
une pour parcourir les colonnes de B,
une pour la somme des produits.
👉
Complexité exponentielle
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
Chaque appel à fibonacci(n) engendre 2 autres appels
→ l’arbre grandit exponentiellement.
Complexité exponentielle
Complexité factorielle
Problème du voyageur de commerce (TSP – brute force)
On a n villes.
L’algorithme naïf teste tous les parcours possibles.
Complexité : O(n!)
QCM – Calcule la complexité
QCM – Calcule la complexité
QCM – Calcule la complexité
QCM – Calcule la complexité
QCM – Calcule la complexité