Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Complexité algorithmique
Notations asymptotiques, méthode de comptage et récursivité

Y. Kharbane

[Link]@[Link]
LEM6 Casablanca

15 mai 2026

LEM6 Casablanca Complexité algorithmique 15 mai 2026 1 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Plan

1 Introduction
2 Notation asymptotique
3 Méthode de comptage
Branches conditionnelles
Boucles for
Boucles while
4 Fonctions et récursivité
5 Relations de récurrence
Établir une relation de récurrence
Récurrences linéaires
Récurrences non linéaires
6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 2 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Plan

1 Introduction
2 Notation asymptotique
3 Méthode de comptage
Branches conditionnelles
Boucles for
Boucles while
4 Fonctions et récursivité
5 Relations de récurrence
Établir une relation de récurrence
Récurrences linéaires
Récurrences non linéaires
6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 3 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Pourquoi étudier la complexité ?

• Pour un même problème, plusieurs algorithmes peuvent exister.

• Ces algorithmes ne sont pas toujours équivalents :
• certains sont rapides ;
• certains consomment beaucoup de mémoire ;
• certains deviennent impraticables lorsque la taille de l’entrée augmente.
• La complexité permet de comparer les algorithmes avant même de les
programmer complètement.

Problème Algorithmes Comparaison

LEM6 Casablanca Complexité algorithmique 15 mai 2026 4 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Un premier exemple : Fibonacci

1 def fibo_rec(n): 1 def fibo_iter(n):

2 if n == 0 or n == 1: 2 if n == 0 or n == 1:
3 return 1 3 return 1
4 else: 4 else:
5 return fibo_rec(n-1) + fibo_rec(n-2) 5 x, y = 1, 1
6 for i in range(2, n+1):
7 x, y = x + y, x
Version récursive naïve 8 return x

Version itérative

Question centrale
Pourquoi ces deux programmes, qui calculent la même chose, n’ont-ils pas la même
efficacité ?

LEM6 Casablanca Complexité algorithmique 15 mai 2026 5 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Deux ressources à mesurer

Complexité temporelle Complexité spatiale

Elle mesure le temps de calcul en fonction Elle mesure la mémoire utilisée en
de la taille de l’entrée. fonction de la taille de l’entrée.
temps

mémoire

LEM6 Casablanca Complexité algorithmique 15 mai 2026 6 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Mesurer indépendamment de la machine

• Le temps réel dépend de plusieurs facteurs : processeur, mémoire, système,

langage, charge de la machine, etc.
• En algorithmique, on utilise donc une unité abstraite : le nombre d’opérations
élémentaires.
• On exprime ce nombre comme une fonction de la taille de l’entrée :

C(n) = nombre d’opérations pour une entrée de taille n.

• On étudie ensuite le comportement de C(n) lorsque n devient grand.

Idée importante
On ne cherche pas le temps exact en secondes, mais l’ordre de grandeur du coût.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 7 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Objectifs du chapitre

À la fin de ce chapitre, il faut savoir :

• comprendre les notations asymptotiques, en particulier O ;
• calculer la complexité d’une suite d’instructions ;
• analyser des conditions, des boucles for et des boucles while ;
• distinguer meilleur cas, pire cas et cas moyen ;
• établir et résoudre des récurrences simples ;
• comparer la complexité temporelle et la complexité spatiale.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 8 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Plan

1 Introduction
2 Notation asymptotique
3 Méthode de comptage
Branches conditionnelles
Boucles for
Boucles while
4 Fonctions et récursivité
5 Relations de récurrence
Établir une relation de récurrence
Récurrences linéaires
Récurrences non linéaires
6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 9 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Comparaison asymptotique

• La comparaison asymptotique consiste à comparer deux fonctions lorsque n

devient très grand.
• En complexité, on ignore souvent :
• les constantes multiplicatives ;
• les termes de plus petit degré ;
• les détails dépendant de la machine.
• Exemple :
3n2 + 5n + 10 se comporte comme n2
lorsque n est grand.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 10 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Définition de la notation O

Définition
Soient f et g deux fonctions positives définies sur N. On dit que f est en O (g) s’il existe
deux constantes C > 0 et n0 ∈ N telles que :

∀n ≥ n0 , f (n) ≤ Cg(n).

g donne une borne supérieure asymptotique de f .

LEM6 Casablanca Complexité algorithmique 15 mai 2026 11 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Interprétation graphique du grand O

Cg(n)
coût

f (n)

À partir de n0 ,
f (n) reste sous Cg(n)
n
n0

LEM6 Casablanca Complexité algorithmique 15 mai 2026 12 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Exemples simples

3n + 7 4n2 + 2n + 1

3n + 7 ≤ 10n pour n ≥ 1 4n2 + 2n + 1 ≤ 7n2 pour n ≥ 1

donc donc
3n + 7 ∈ O (n). 4n2 + 2n + 1 ∈ O (n2 ).

À retenir
En pratique, on garde le terme qui grandit le plus vite.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 13 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Classes de complexité usuelles

Notation Nom Exemple typique

O (1) constante accès à un élément
O (log n) logarithmique recherche dichotomique
O (n) linéaire parcours d’une liste
O (n log n) quasi-linéaire tri fusion
O (n2 ) quadratique deux boucles imbriquées
O (n3 ) cubique trois boucles imbriquées
O (2n ) exponentielle Fibonacci récursif naïf
O (n!) factorielle permutations complètes

LEM6 Casablanca Complexité algorithmique 15 mai 2026 14 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Hiérarchie des croissances

1 log n n n log n n2 n3 2n n!

croissance

Lecture
Plus on avance vers la droite, plus le coût devient important pour les grandes valeurs de
n.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 15 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Quelques ordres de grandeur

n log2 n n n2 2n
10 ≈3 10 100 1024
100 ≈7 100 10 000 énorme
1000 ≈ 10 1000 1 000 000 impraticable

Conséquence
Un algorithme en O (n2 ) peut être acceptable pour n = 1000, mais un algorithme en
O (2n ) devient très vite impossible à utiliser.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 16 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Règles de calcul avec O

Soient f , g et h des fonctions positives.

• Si f ∈ O (g) et g ∈ O (h), alors f ∈ O (h).
• Si f ∈ O (g), alors kf ∈ O (g) pour toute constante k > 0.
• Si f1 ∈ O (g1 ) et f2 ∈ O (g2 ), alors :

f1 + f2 ∈ O max(g1 , g2 ) .
¡ ¢

• Si f1 ∈ O (g1 ) et f2 ∈ O (g2 ), alors :

f1 f2 ∈ O (g1 g2 ).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 17 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Exercice

Donner l’ordre de grandeur des fonctions suivantes :

1 f (n) = 7n + 100 ;
2 g(n) = 3n2 + 10n + 5 ;
3 h(n) = n log n + 4n ;
4 u(n) = 2n3 + n2 + 106 .

LEM6 Casablanca Complexité algorithmique 15 mai 2026 18 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Exercice

Donner l’ordre de grandeur des fonctions suivantes :

1 f (n) = 7n + 100 ;
2 g(n) = 3n2 + 10n + 5 ;
3 h(n) = n log n + 4n ;
4 u(n) = 2n3 + n2 + 106 .

Correction

f (n) ∈ O (n), g(n) ∈ O (n2 ), h(n) ∈ O (n log n), u(n) ∈ O (n3 ).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 18 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Plan

1 Introduction
2 Notation asymptotique
3 Méthode de comptage
Branches conditionnelles
Boucles for
Boucles while
4 Fonctions et récursivité
5 Relations de récurrence
Établir une relation de récurrence
Récurrences linéaires
Récurrences non linéaires
6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 19 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Principe de la méthode de comptage

On analyse un programme séquentiel en trois étapes :

1 attribuer un coût aux instructions fondamentales ;
2 compter le nombre d’exécutions de chaque instruction ;
3 additionner les coûts et garder l’ordre de grandeur dominant.

Coût local Nombre d’exécutions Coût global

LEM6 Casablanca Complexité algorithmique 15 mai 2026 20 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Instructions simples

On considère généralement comme instructions simples :

• lecture ou écriture d’une variable ;
• affectation ;
• comparaison simple ;
• addition, soustraction, multiplication de nombres de taille raisonnable ;
• accès à une case d’un tableau ou d’une liste.

Coût
Une instruction simple est comptée en temps constant : O (1).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 21 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Attention aux fausses instructions simples

Certaines opérations Python peuvent cacher un coût important :

1 y = a ** b # puissance : depend de b
2 T = L[:] # copie de liste : O(n)
3 T = [Link]() # copie de liste : O(n)
4 M = L[i:j] # slicing : O(j-i)
5 R = L1 + L2 # concatenation : O(len(L1)+len(L2))

Attention
Lorsqu’on analyse un programme Python, il faut savoir si une opération manipule un
seul élément ou toute une structure.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 22 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Suite d’instructions

Si un programme exécute successivement plusieurs traitements :

Traitement1 , Traitement2 , . . . , Traitementk ,

et si leurs coûts sont respectivement :

O (f1 (n)), O (f2 (n)), . . . , O (fk (n)),

alors le coût total est :

O f1 (n) + f2 (n) + · · · + fk (n) .
¡ ¢

Simplification
On conserve le terme dominant.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 23 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Exemple : deux traitements successifs

1 s = 0
2 for i in range(n):
3 p = 1
4 for j in range(i):
5 p = p * i
6 s = s + p
7
8 t = 0
9 for i in range(n):
10 t = t + i

• Le premier bloc contient une double boucle : O (n2 ).

• Le deuxième bloc est linéaire : O (n).
• Le coût total est : O (n2 + n) = O (n2 ).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 24 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

1 Introduction

2 Notation asymptotique

3 Méthode de comptage
Branches conditionnelles
Boucles for
Boucles while

4 Fonctions et récursivité

5 Relations de récurrence

6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 25 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Condition simple

1 if c: • Coût de la condition : O (f (n)).

2 Traitement
• Coût du traitement : O (g(n)).

Complexité
• Meilleur cas : la condition est fausse, coût O (f (n)).
• Pire cas : la condition est vraie, coût O (f (n) + g(n)).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 26 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Condition avec alternative

1 if c:
2 Traitement_1
3 else:
4 Traitement_2

• Coût de la condition : O (f (n)).

• Coût du premier traitement : O (g1 (n)).
• Coût du deuxième traitement : O (g2 (n)).

Pire cas = O f (n) + max(g1 (n), g2 (n)) .

¡ ¢

LEM6 Casablanca Complexité algorithmique 15 mai 2026 27 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Exemple : branchement

1 if a > b:
2 s = 0
3 for i in range(n):
4 for j in range(i):
5 s = s + i*j
6 else:
7 t = 0
8 for i in range(n):
9 t = t + i

• Le test a > b coûte O (1).

• La branche if coûte O (n2 ).
• La branche else coûte O (n).
• Au pire : O (n2 ).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 28 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Branches conditionnelles

1 if c_1: Si le coût de chaque condition ci est O (fi ), et le coût de

2 Traitement_1 chaque bloc d’instructions Traitementi est O (gi ) alors :
3 elif c_2:
4 Traitement_2 • Le coût au meilleur des cas est :
5 . Ã Ã ! !
6 . i n−1
O (fj ) + O (gi ) , O (fj ) + O (gn )
X X
7 . min min
8 else: 1≤i≤n−1 j=1 j=1
9 Traitement_n
• Le coût au pire des cas est :
à à ! !
i n−1
O (fj ) + O (gi ) , O (fj ) + O (gn )
X X
max max
1≤i≤n−1 j=1 j=1

LEM6 Casablanca Complexité algorithmique 15 mai 2026 29 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

1 Introduction

2 Notation asymptotique

3 Méthode de comptage
Branches conditionnelles
Boucles for
Boucles while

4 Fonctions et récursivité

5 Relations de récurrence

6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 30 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Boucle for

1 for i in range(a, b): Si le coût du bloc d’instructions Traitement lors de

2 Traitement chaque itération i est O (fi ) alors le coût est :

b−1
O (fi )
X
i=a

LEM6 Casablanca Complexité algorithmique 15 mai 2026 31 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Boucle for

1 for x in seq: Si le coût du bloc d’instructions Traitement lors de

2 Traitement chaque itération i est O (fi ) alors le coût est :

taille(seq)
O (fi )
X
i=1

LEM6 Casablanca Complexité algorithmique 15 mai 2026 32 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Remarque :

On distinguera entre le meilleur des cas et le pire des cas lorsque :

• Le corps de la boucle for contient une instruction qui permet de quitter la boucle
selon une condition.

• Le coût du corps de la boucle dans le meilleur des cas diffère de celui du pire des
cas.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 33 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Exemple : test de primalité naïf

1 def est_premier(n):
2 for i in range(2, n//2 + 1):
3 if n % i == 0:
4 return False
5 return True

• Si n est divisible rapidement, la boucle s’arrête tôt.

• Dans le meilleur cas, lorsque n est pair, la boucle s’arrêtera dès la première
itération, la complexité sera : O (1)
• Dans le pire cas, on teste tous les diviseurs possibles jusqu’à n/2.
• Complexité au pire : O (n).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 34 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

1 Introduction

2 Notation asymptotique

3 Méthode de comptage
Branches conditionnelles
Boucles for
Boucles while

4 Fonctions et récursivité

5 Relations de récurrence

6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 35 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Boucle while

1 while c : Si le coût de la condition c est O (f ), et le coût du bloc

2 Traitement d’instructions Traitement lors de chaque itération i est
O (gi ) alors le coût est :

nbi
O (f ) + O (gi ) + O (f )
X¡ ¢
i=1

Tel que nbi est le nombre d’itérations qu’effectuera la

boucle while.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 36 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Exemple :

1 i = 1
2 s = 0
3 while i <= n:
4 s = s + i
5 i = 2*i

Itération 1 2 3 ··· k
i 1 2 4 ··· 2k−1

Lors de l’arrêt de la boucle à la dernière itération, 2k−1 ≤ n, donc k = O (log n).

C(n) = O (log n).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 37 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Méthode pratique pour une boucle while

1 Identifier la variable qui contrôle l’arrêt.

2 Écrire son évolution à chaque itération.
3 Déterminer après combien d’itérations la condition devient fausse.
4 Multiplier par le coût d’une itération.

À retenir
Une boucle while n’est pas automatiquement en O (n) : elle peut être constante,
linéaire, logarithmique, quadratique, etc.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 38 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Plan

1 Introduction
2 Notation asymptotique
3 Méthode de comptage
Branches conditionnelles
Boucles for
Boucles while
4 Fonctions et récursivité
5 Relations de récurrence
Établir une relation de récurrence
Récurrences linéaires
Récurrences non linéaires
6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 39 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Complexité d’une fonction

• La complexité d’une fonction est exprimée en fonction de la taille de son entrée.

• Pour une fonction non récursive, on analyse son corps comme un programme
ordinaire.
• Pour une fonction récursive, on exprime souvent le coût par une relation de
récurrence.

Fonction

Itérative Récursive

LEM6 Casablanca Complexité algorithmique 15 mai 2026 40 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Somme inverse :

1 def somme_inverse(n):
2 s = 0
3 for i in range(1, n+1):
4 s = s + 1/i
5 return s

• Taille de l’entrée : n.
• La boucle fait n itérations.
• Le corps coûte O (1).

C(n) = O (n).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 41 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Fibonacci itératif :

1 def fibo(n):
2 if n <= 1:
3 return 1
4 x, y = 1, 1
5 for i in range(2, n+1):
6 x, y = x + y, x
7 return x

• Une seule boucle de longueur n.

• Chaque itération coûte O (1).
• Complexité temporelle : O (n).
• Mémoire supplémentaire : O (1).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 42 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Recherche séquentielle et recherche dichotomique

1 def recherche_seq(L, x): 1 def recherche_dicho(L, x):

2 for i in range(len(L)): 2 deb = 0
3 if L[i] == x: 3 fin = len(L)-1
4 return True 4 while deb <= fin:
5 return False 5 m = (deb+fin)//2
6 if L[m] == x:
O (n) 7 return True
8 elif L[m] < x:
9 deb = m+1
10 else:
11 fin = m-1
12 return False

O (log n)

LEM6 Casablanca Complexité algorithmique 15 mai 2026 43 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Tri par sélection

1 def indice_max(L, k):

2 imax = 0
3 for i in range(1, k):
4 if L[imax] < L[i]:
5 imax = i
6 return imax
7
8 def tri_selection(L):
9 n = len(L)
10 for i in range(n, 0, -1):
11 j = indice_max(L, i)
12 if i-1 != j:
13 L[i-1], L[j] = L[j], L[i-1]

O (n2 ).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 44 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Tri par insertion

1 def tri_insertion(L):
2 n = len(L)
3 for i in range(1, n):
4 x = L[i]
5 j = i - 1
6 while j >= 0 and L[j] > x:
7 L[j+1] = L[j]
8 j = j - 1
9 L[j+1] = x

• Meilleur cas : la liste est déjà triée, coût O (n).

• Pire cas : la liste est triée dans l’ordre inverse, coût O (n2 ).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 45 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Plan

1 Introduction
2 Notation asymptotique
3 Méthode de comptage
Branches conditionnelles
Boucles for
Boucles while
4 Fonctions et récursivité
5 Relations de récurrence
Établir une relation de récurrence
Récurrences linéaires
Récurrences non linéaires
6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 46 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

1 Introduction

2 Notation asymptotique

3 Méthode de comptage

4 Fonctions et récursivité

5 Relations de récurrence
Établir une relation de récurrence
Récurrences linéaires
Récurrences non linéaires

6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 47 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Méthodologie de modélisation

Pour évaluer la complexité T (n) d’un algorithme récursif, on procède en trois étapes :

1 Taille de l’entrée : Identifier le paramètre n mesurant la taille des données à traiter.

2 Cas de base : Déterminer le coût des instructions exécutées pour la condition
d’arrêt (généralement constant, O (1)).
3 Cas récursif : Décomposer le travail effectué en :
• Le nombre d’appels récursifs (a).
• La taille des sous-problèmes résolus (ex : n − 1, n/2).
• Le coût local f (n) des opérations de division et de recombinaison.

Forme générale

T (n) = a · T (taille_sous_problème) + f (n)

LEM6 Casablanca Complexité algorithmique 15 mai 2026 48 / 74

 Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Exemple 1 : Recherche dichotomique récursive

1 def recherche_dicho_rec(L, x, g, d):

Analyse :
2 if g > d:
3 return False • Taille : n = d − g.
4 m = (g + d) // 2
5 if L[m] == x: • Cas de base : g > d, coût O (1).
6 return True
7 elif L[m] < x:
• Coût local : Calcul de m et
8 return recherche_dicho_rec(L, x, m+1, comparaisons coûtent O (1).
d)
9 else: • Appel récursif : Au pire cas, un seul
10 return recherche_dicho_rec(L, x, g, m appel sur une moitié presque de la liste
-1)
(n/2).

Relation de récurrence
n
T (n) ≤ T ( ) + O (1)
2

LEM6 Casablanca Complexité algorithmique 15 mai 2026 49 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Exemple 2 : Tri fusion (Merge Sort)

1 def tri_fusion(L):
Analyse :
2 n = len(L)
3 if n <= 1: • Taille : n = len(L).
4 return L
5 m = n // 2 • Cas de base : n ≤ 1, coût O (1).
6 G = tri_fusion(L[:m])
7 D = tri_fusion(L[m:])
• Appels récursifs : Deux appels sur des
8 return fusion(G, D) listes de taille n/2.
• Coût local : La fonction fusion
parcourt les deux listes pour les
recomposer, ce qui coûte O (n).

Relation de récurrence

T (n) = 2T (n/2) + O (n)

LEM6 Casablanca Complexité algorithmique 15 mai 2026 50 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

1 Introduction

2 Notation asymptotique

3 Méthode de comptage

4 Fonctions et récursivité

5 Relations de récurrence
Établir une relation de récurrence
Récurrences linéaires
Récurrences non linéaires

6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 51 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Relation de récurrence linéaire :

Une récurrence linéaire à coefficients constants d’ordre k est de la forme :

ck T (n) + ck−1 T (n − 1) + · · · + c0 T (n − k) = f (n)

Avec les conditions initiales :

T (n0 ) = d0 , . . . , T (n0 + k − 1) = dk−1

LEM6 Casablanca Complexité algorithmique 15 mai 2026 52 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Equation caractéristique :

Soit la récurrence linéaire d’ordre k suivante :

ck T (n) + ck−1 T (n − 1) + · · · + c0 T (n − k) = f (n)

T (n0 ) = d0 , . . . , T (n0 + k − 1) = dk−1

L’équation caractéristique associée à cette relation est la suivante :

ck r k + ck−1 r k−1 + · · · + c0 = f (n)

LEM6 Casablanca Complexité algorithmique 15 mai 2026 53 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Théorème :

Soit l’équation caractéristique suivante :

ck r k + ck−1 r k−1 + · · · + c0 = 0

La solution générale de cette équation est de la forme :

( )
l mX
i −1
rin j
X
T (n) = aij n
i=1 j=0

LEM6 Casablanca Complexité algorithmique 15 mai 2026 54 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Opérateur d’avancement :

Etant donnée une suite de nombres entiers f (n), l’opérateur d’avancement E est défini
comme suit :

f (n) = c (une constante) → E(f (n)) = c

f (n) ̸= c (une constante) → E(f (n)) = f (n + 1)

LEM6 Casablanca Complexité algorithmique 15 mai 2026 55 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Opérateur d’avancement :

D’autres opérateurs peuvent aussi être créés en combinant l’opérateur à lui-même ou à

des constantes. Pour ce faire, on définit pour la constante c l’opérateur de même nom c
comme suit :

c(f (n)) = c × f (n)

LEM6 Casablanca Complexité algorithmique 15 mai 2026 56 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Opérateur d’avancement :

La multiplication et l’addition d’opérateurs sont définies comme suit :

(E1 × E2 )f (n) = E1 (E2 (f (n)))

(E1 + E2 )f (n) = E1 (f (n)) + E2 (f (n))

La multiplication et l’addition des opérateurs sont commutatives et associatives.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 57 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Opérateur d’avancement :

Terme à éliminer Eliminateur correspondant

O (1) (E − 1)

O (nk ) (E − 1)k+1

O (an ) (E − a)

O (an nk ) (E − a)k+1

LEM6 Casablanca Complexité algorithmique 15 mai 2026 58 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Exemple : Fibonacci

1 def fibo(n):
2 if n <= 1:
3 return 1 T (0) = T (1) = O (1)
4 else:
5 return fibo(n-1) + fibo(n-2) Pour n > 1 :

T (n) = T (n − 1) + T (n − 2) + O (1)

LEM6 Casablanca Complexité algorithmique 15 mai 2026 59 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Exemple : Fibonacci (suite)

En appliquant l’opérateur (E − 1) pour éliminer la constante :

T (n + 1) − T (n) = T (n) − T (n − 1) + T (n − 1) − T (n − 2)
=⇒ T (n + 1) − 2T (n) + T (n − 2) = 0
L’équation caractéristique est :
r 3 − 2r 2 + 1 = 0 =⇒ (r − 1)(r 2 − r − 1) = 0
p p
Les racines sont : 1, 1+2 5 , 1−2 5 . La solution générale est donc :
p !n
à à p !n
1 + 5 1 − 5
T (n) = α1n + β +γ
2 2
Ce qui donne asymptotiquement :
ÃÃ p !n !
1+ 5
T (n) = O
2
LEM6 Casablanca Complexité algorithmique 15 mai 2026 60 / 74
Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Arbre d’appels de Fibonacci

F(n)

F(n − 1) F(n − 2)

F(n − 2) F(n − 3) F(n − 3) F(n − 4)

··· ···

Problème
Les mêmes valeurs sont recalculées plusieurs fois.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 61 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

1 Introduction

2 Notation asymptotique

3 Méthode de comptage

4 Fonctions et récursivité

5 Relations de récurrence
Établir une relation de récurrence
Récurrences linéaires
Récurrences non linéaires

6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 62 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Récurrences non linéaires

• Contrairement aux récurrences linéaires, les récurrences non linéaires (souvent

issues de stratégies "diviser pour régner") expriment la complexité en fonction de
sous-problèmes dont la taille est une fraction de la taille initiale.
• Par exemple, une forme typique est T (n) = aT (n/b) + f (n).
• Pour résoudre ces types de relations de récurrence, nous allons utiliser
principalement la méthode de substitution.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 63 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Etapes d’analyse en utilisant la méthode de substitution

La méthode de substitution est souvent décrite de manière célèbre en deux étapes :

• Deviner la forme de la solution.

• Utiliser la preuve d’induction pour montrer la validité de notre conjecture.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 64 / 74

 Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Application : (exponentiation rapide)

1 def puissance(x, n):

2 if n == 0: T (0) = T (1) = O (1)
3 return 1
4 elif n == 1: Si n ≥ 2 et pair,
5 return x
6 elif n % 2 == 0: ³n´
7 y = puissance(x, n//2) T (n) = T + O (1)
8 return y*y 2
9 else:
10 y = puissance(x, (n-1)//2) Si n ≥ 2 et impair,
11 return y*y*x
n−1
µ ¶
T (n) = T + O (1)
2

LEM6 Casablanca Complexité algorithmique 15 mai 2026 65 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Application : (exponentiation rapide)

¡n¢
Supposons (∃α > 0) tel que T (n) ≤ T 2+α :
³n´
T (n) ≤ T +α
³ 2n ´
T (n) ≤ T 2 + 2α
2
..
.
n
µ ¶
T (n) ≤ T k + kα
2
n
On s’arrête lorsque 2k
= 1 =⇒ k = log2 n.

T (n) ≤ T (1) + α log n

Ce qui donne :
T (n) = O (log n)
LEM6 Casablanca Complexité algorithmique 15 mai 2026 66 / 74
Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Application : (exponentiation rapide)

Preuve par induction :

• Cas de base : n = 2,
T (2) = T (1) + O (1) = O (1)
• Hérédité :
• Si n est pair,
³n´ ³ n´ ³ n ´
T (n) = T + O (1) = O log + O (1) = O log + 1 = O (log n)
2 2 2
• Si n est impair,

n−1 n−1
¶
µ µ ¶
T (n) = T + O (1) = O log + O (1) = O (log n)
2 2

LEM6 Casablanca Complexité algorithmique 15 mai 2026 67 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Plan

1 Introduction
2 Notation asymptotique
3 Méthode de comptage
Branches conditionnelles
Boucles for
Boucles while
4 Fonctions et récursivité
5 Relations de récurrence
Établir une relation de récurrence
Récurrences linéaires
Récurrences non linéaires
6 Complexité spatiale

LEM6 Casablanca Complexité algorithmique 15 mai 2026 68 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Définition de la complexité spatiale

• La complexité spatiale mesure la quantité de mémoire utilisée par un algorithme.

• Elle dépend de la taille de l’entrée.
• Elle peut inclure :
• variables locales ;
• tableaux auxiliaires ;
• copies de listes ;
• pile d’appels récursifs.

Même notation
On utilise aussi la notation O pour la mémoire.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 69 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Tri à bulles : mémoire constante

1 def tri_bulles(L):
2 n = len(L)
3 for i in range(n-1, -1, -1):
4 for j in range(i):
5 if L[j] > L[j+1]:
6 L[j], L[j+1] = L[j+1], L[j]

• Le tri modifie la liste sur place.

• Il n’utilise que quelques variables auxiliaires.

Complexité spatiale supplémentaire = O (1).

LEM6 Casablanca Complexité algorithmique 15 mai 2026 70 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Tri rapide avec listes auxiliaires

1 def tri_rapide(L):
2 n = len(L)
3 if n <= 1:
4 return L
5 PP = [L[0]]
6 PG, PD = [], []
7 for i in range(1, n):
8 if L[i] > L[0]:
9 [Link](L[i])
10 else:
11 [Link](L[i])
12 return tri_rapide(PG) + PP + tri_rapide(PD)

Observation
Cette version crée de nouvelles listes à chaque appel : la mémoire n’est pas constante.

LEM6 Casablanca Complexité algorithmique 15 mai 2026 71 / 74

 Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Fibonacci : trois versions

1 def fibo_rec(n): 1 def fibo_tab(n): 1 def fibo_var(n):

2 if n <= 1: 2 T = [0]*(n+1) 2 x, y = 1, 1
3 return 1 3 T[0] = T[1] = 1 3 for i in range(2, n+1):
4 return fibo_rec(n-1) + 4 for i in range(2, n+1): 4 x, y = x+y, x
fibo_rec(n-2) 5 T[i] = T[i-1] + T[i-2] 5 return x
6 return T[n]
p ´n ´
Temps : O (n), espace : O (1)
³³
1+ 5
Temps : O 2 Temps : O (n), espace : O (n)

LEM6 Casablanca Complexité algorithmique 15 mai 2026 72 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Temps ou mémoire ?

• Un algorithme peut être rapide mais consommer beaucoup de mémoire.

• Un autre peut être plus lent mais utiliser très peu de mémoire.
• Le bon choix dépend du contexte :
• taille des données ;
• mémoire disponible ;
• besoin de rapidité ;
• simplicité d’implémentation.

Temps Mémoire

Compromis

LEM6 Casablanca Complexité algorithmique 15 mai 2026 73 / 74

Introduction Notation asymptotique Méthode de comptage Fonctions et récursivité Relations de récurrence Complexité spatiale

Merci pour votre attention

LEM6 Casablanca Complexité algorithmique 15 mai 2026 74 / 74