Complexité Algorithmique

El Houssaine OUTFARDINE

CPGE Tanger
Lycee Moulay EL-Hassan
[Link]@[Link]
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Plan

1 Introduction

2 Calcul du coût d’un algorithme

3 Type de complexité

4 Complexité asymptotique

5 Complexité des fonctions récursives

Récursivités simples
Suites non-linéaires de type "diviser pour régner"
Résolution par substitution répétitive
Résolution par induction

6 complexité spatiale

Complexité Algorithmique 1 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Exercice
Ecrire en python une fonction qui prend en argument une chaîne de caractères et
détermine si le caractère ’a’ est présent dans la chaîne (on retourne soit True soit False).

Complexité Algorithmique 2 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Solution 1 :
def contienta1(chaine):
k=0
N=len(chaine)
trouve=False
while(trouve == False and k < N):
if chaine[k]=='a':
trouve = True
k=k+1
return trouve
Solution 2 :
def contienta2(chaine):
for i in range(len(chaine)):
if chaine[i]=='a':
return True
return False

Complexité Algorithmique 3 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Solution 3 :
def contienta3(chaine):
n=[Link]('a')
return bool(n)
Solution 4 :
def contienta4 (chaine):
return ('a' in chaine)

Complexité Algorithmique 4 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Solution 3 :
def contienta3(chaine):
n=[Link]('a')
return bool(n)
Solution 4 :
def contienta4 (chaine):
return ('a' in chaine)

1 Le code le plus court ! Est-il meilleur ?

2 Comment peut-on désigner le meilleur code parmi ces quatre solutions ?

Complexité Algorithmique 4 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Solution 3 :
def contienta3(chaine):
n=[Link]('a')
return bool(n)
Solution 4 :
def contienta4 (chaine):
return ('a' in chaine)

1 Le code le plus court ! Est-il meilleur ?

2 Comment peut-on désigner le meilleur code parmi ces quatre solutions ?

Remarque 1
on s’intéressera plus, dans ce cours, à la complexité temporelle.
On ne mesure pas le temps d’exécution des algorithmes d’une façon expérimentale car ces
mesures vont dépendre de la machine utilisée. On estime donc ce temps d’exécution d’une
façon théorique en utilisant des unités de temps abstraites correspondant au nombre
d’opérations effectuées.

Complexité Algorithmique 4 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Introduction
La complexité d’un algorithme est une mesure de la quantité de ressources nécessaires
à son exécution. On distingue deux types de complexité :
Complexité temporelle : mesure le temps de calcul consommé lors de l’exécution
d’un programme.
Complexité spatiale : mesure le nombre d’emplacement mémoire occupé lors de
l’exécution d’un programme.

Complexité Algorithmique 5 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Introduction
La complexité d’un algorithme est une mesure de la quantité de ressources nécessaires
à son exécution. On distingue deux types de complexité :
Complexité temporelle : mesure le temps de calcul consommé lors de l’exécution
d’un programme.
Complexité spatiale : mesure le nombre d’emplacement mémoire occupé lors de
l’exécution d’un programme.

Remarque 2
1 Dans ce cours on s’intéresse à la complexité temporelle.
2 On ne mesure pas le temps d’exécution des algorithmes d’une façon expérimentale car ces
mesures vont dépendre de la machine utilisée. On estime donc ce temps d’exécution d’une
façon théorique en utilisant des unités de temps abstraites correspondant au nombre
d’opérations effectuées.
3 La complexité d’un programme peut augmenter quand la taille des données d’entrée
devient importante. Nous estimerons par conséquent la complexité d’un algorithme
comme fonction de la taille (ou valeurs) des données d’entrée qu’on appel un paramètre
de complexité.

Complexité Algorithmique 5 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

opération de base
On appelle opération de base, ou opération élémentaire, toute :
Affectation
Test de comparaison : ==, ≥, ≤, != ...
Opération de lecture et écriture
Opération arithmétique : +, -,*, / ....
On considère que toutes ces opérations élémentaires ont le même coût qui égale à 1,
indépendamment des données d’entrée.

Complexité Algorithmique 6 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

opération de base
On appelle opération de base, ou opération élémentaire, toute :
Affectation
Test de comparaison : ==, ≥, ≤, != ...
Opération de lecture et écriture
Opération arithmétique : +, -,*, / ....
On considère que toutes ces opérations élémentaires ont le même coût qui égale à 1,
indépendamment des données d’entrée.

Ainsi, si on considère deux blocs d’instructions P et Q avec CP est le cout du bloc P et

CQ est le cout du bloc Q, alors le cout total est : CP + CQ

Exemple 1
S=1 # instruction 1
S=S*n # instruction 2
S=S-n # instruction 3
Complexité :
Cinstruction1 + Cinstruction2 + Cinstruction3 = 1 + 2 + 2 = 5

Complexité Algorithmique 6 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Coût d’une instruction conditionnelle

if test :
# block d'instruction Q
else :
# block d'instruction P

Complexité Algorithmique 7 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Coût d’une instruction conditionnelle

if test :
# block d'instruction Q
else :
# block d'instruction P
Complexité :
C ≤ Ctest + max(CQ , CP )

Complexité Algorithmique 7 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Coût d’une instruction conditionnelle

if test :
# block d'instruction Q
else :
# block d'instruction P
Complexité :
C ≤ Ctest + max(CQ , CP )

Exemple 2

if i % 2= = 0 : #test
n = i // 2 #bloc 1
else :
i = i+1 #bloc 2
n = i #bloc 2

Complexité Algorithmique 7 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Coût d’une instruction conditionnelle

if test :
# block d'instruction Q
else :
# block d'instruction P
Complexité :
C ≤ Ctest + max(CQ , CP )

Exemple 2

if i % 2= = 0 : #test
n = i // 2 #bloc 1
else :
i = i+1 #bloc 2
n = i #bloc 2

C ≤ Ctest + max(CQ , CP ) ≤ 2 + max(2, 4) ≤ 6

Complexité Algorithmique 7 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

coût d’une boucle

for i in range(n):
# Bloc d'instructions Q

Complexité Algorithmique 8 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

coût d’une boucle

for i in range(n):
# Bloc d'instructions Q

Complexité :
n−1
C= ∑ CQ
i=0

Complexité Algorithmique 8 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

coût d’une boucle

for i in range(n):
# Bloc d'instructions Q

Complexité :
n−1
C= ∑ CQ
i=0

while test :
# Bloc d'instructions Q

Complexité Algorithmique 8 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

coût d’une boucle

for i in range(n):
# Bloc d'instructions Q

Complexité :
n−1
C= ∑ CQ
i=0

while test :
# Bloc d'instructions Q

Complexité :
C= ∑ Ctest + ∑ CQ

Complexité Algorithmique 8 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

coût d’une boucle

Exemple 3

s=0
for i in range(n+1):
s=s+1

Complexité Algorithmique 9 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

coût d’une boucle

Exemple 3

s=0
for i in range(n+1):
s=s+1

Compléxité :
n n
C = 1 + ∑ Ctest = 1 + ∑ 2 = 1 + 2(n + 1) = 2n + 3
0 0

Complexité Algorithmique 9 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

coût d’une boucle

Exemple 4

for i in range(n):
for j in range(n):
s=s+1 # instruction 1
print(s) # instruction 2

Complexité Algorithmique 10 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

coût d’une boucle

Exemple 4

for i in range(n):
for j in range(n):
s=s+1 # instruction 1
print(s) # instruction 2

Compléxité :

n−1 i−1 n−1 i−1 n−1 i−1 n−1

n(n − 1)
C= ∑ ∑ (C1 + C2 ) = ∑ ∑ (2 + 1) = ∑ ∑ 3 = ∑ 3i = 3 2
i=0 j=0 i=0 j=0 i=0 j=0 i=0

Complexité Algorithmique 10 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

coût d’une boucle

Exemple 5

i=0
s=0
while i <= n):
s=s+i # instruction 1
i=i+1 # instruction 2

Complexité Algorithmique 11 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

coût d’une boucle

Exemple 5

i=0
s=0
while i <= n):
s=s+i # instruction 1
i=i+1 # instruction 2

Compléxité :

n+1 n n+1 n
C = 2+ ∑ Ctest + ∑ (C1 + C2 ) = 2 + ∑ 1 + ∑ (2 + 2)
i=0 i=0 i=0 i=0

= 2 + n + 2 + 4(n + 1) = 5n + 8

Complexité Algorithmique 11 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Appel d’une fonction

Lorsqu’une fonction ou une procédure est appelée, le cout de cette fonction ou

procédure est le nombre total d’opérations élémentaires engendrées par l’appel de
cette fonction.

Complexité Algorithmique 12 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Type de complexité

Pour des données d’entrée de même taille, un algorithme n’effectue pas

nécessairement le même nombre d’opérations élémentaires. C’est pour ça on distingue
3 types de complexité :
Meilleur des cas : C’est un minorant du temps d’exécution pour toutes les entrées
possibles d’une même taille.

Complexité Algorithmique 13 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Type de complexité

Pour des données d’entrée de même taille, un algorithme n’effectue pas

nécessairement le même nombre d’opérations élémentaires. C’est pour ça on distingue
3 types de complexité :
Meilleur des cas : C’est un minorant du temps d’exécution pour toutes les entrées
possibles d’une même taille.
Pire des cas : C’est un majorant du temps d’exécution possible pour toutes les
entrées possibles d’une même taille.

Complexité Algorithmique 13 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Type de complexité

Pour des données d’entrée de même taille, un algorithme n’effectue pas

nécessairement le même nombre d’opérations élémentaires. C’est pour ça on distingue
3 types de complexité :
Meilleur des cas : C’est un minorant du temps d’exécution pour toutes les entrées
possibles d’une même taille.
Pire des cas : C’est un majorant du temps d’exécution possible pour toutes les
entrées possibles d’une même taille.
complexité en moyenne : C’est une moyenne de la complexité, pondérée entre les
différentes entrées possibles : C = ∑pour toute entre d p(d) ∗ Cd
avec p(d) probabilité d’apparition de l’entrée d et Cd son temps. d’exécution

Complexité Algorithmique 13 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Type de complexité

Pour des données d’entrée de même taille, un algorithme n’effectue pas

nécessairement le même nombre d’opérations élémentaires. C’est pour ça on distingue
3 types de complexité :
Meilleur des cas : C’est un minorant du temps d’exécution pour toutes les entrées
possibles d’une même taille.
Pire des cas : C’est un majorant du temps d’exécution possible pour toutes les
entrées possibles d’une même taille.
complexité en moyenne : C’est une moyenne de la complexité, pondérée entre les
différentes entrées possibles : C = ∑pour toute entre d p(d) ∗ Cd
avec p(d) probabilité d’apparition de l’entrée d et Cd son temps. d’exécution

Remarque 3
Généralement, on s’intéresse à la complexité dans le pire des cas, car cela correspond à la
performance de l’algorithme lorsqu’il prend le plus de temps : il ne prendra jamais plus de
temps que ce qu’on a estimé.

Complexité Algorithmique 13 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Type de complexité

Exemple 6
recherche d’un élément X dans un tableau T :
def recherche(X,T):
n=len(T)
for i in range(n):
if X == T[i]:
return True
return False

Complexité Algorithmique 14 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Type de complexité

Exemple 6
recherche d’un élément X dans un tableau T :
def recherche(X,T):
n=len(T)
for i in range(n):
if X == T[i]:
return True
return False

Meilleur des cas : lorsque X est égal au premier élément de T. On effectue donc
une comparaison et un return, d’où C = 4

Complexité Algorithmique 14 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Type de complexité

Exemple 6
recherche d’un élément X dans un tableau T :
def recherche(X,T):
n=len(T)
for i in range(n):
if X == T[i]:
return True
return False

Meilleur des cas : lorsque X est égal au premier élément de T. On effectue donc
une comparaison et un return, d’où C = 4
Pire des cas : lorsque X n’est pas dans T ou bien il est le dernier. On effectue
n = len(T ) comparaisons et un return C = 2 + ∑ni=−01 1 + 1 = 3 + n

Complexité Algorithmique 14 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Type de complexité

complexité en moyenne : Soit p la probabilité que X est dans le tableau T, alors :

p
La probabilité que X se trouve dans la ime case est n puisqu’il peut se trouver dans
n’importe quelle case avec la même probabilité.
La probabilité que X ne soit pas dans le tableau T est (1 − p)

Complexité Algorithmique 15 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Type de complexité

complexité en moyenne : Soit p la probabilité que X est dans le tableau T, alors :

p
La probabilité que X se trouve dans la ime case est n puisqu’il peut se trouver dans
n’importe quelle case avec la même probabilité.
La probabilité que X ne soit pas dans le tableau T est (1 − p)
Donc, Le coût dépend de nombre de comparaisons effectuées :
- Si X est dans la ime case de T alors on effectuera i comparaisons.
- Si X n’est pas dans T alors on effectuera n comparaisons.

Complexité Algorithmique 15 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Type de complexité

complexité en moyenne : Soit p la probabilité que X est dans le tableau T, alors :

p
La probabilité que X se trouve dans la ime case est n puisqu’il peut se trouver dans
n’importe quelle case avec la même probabilité.
La probabilité que X ne soit pas dans le tableau T est (1 − p)
Donc, Le coût dépend de nombre de comparaisons effectuées :
- Si X est dans la ime case de T alors on effectuera i comparaisons.
- Si X n’est pas dans T alors on effectuera n comparaisons.
D’où :
n−1
p p n(n + 1) p(n + 1)
C = 2+ ∑ n
i + n(1 − p) = 2 +
n 2
+ n(1 − p) = 2 +
2
+ n(1 − p)
i=0

Si on est sur que X appartient au tableau T (p=1) alors :

(n + 1)
C = 2+
2

Complexité Algorithmique 15 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O
Il est souvent inutile d’évaluer de façon exacte le nombre d’opérations effectuées par
un algorithme, on fait recours donc à une approximation de ce nombre d’opérations
représentant ce qu’on appel ordre de grandeur de la complexité.

Définition 1
On dit que une fonction f est dominée par une fonction g si et seulement si :

∃n0 , c > 0 tq f (n) ≤ c.g(n) ∀n ≥ n0

On notera f = O(g) et on dit que f est du même ordre de grandeur que g

Complexité Algorithmique 16 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O
Il est souvent inutile d’évaluer de façon exacte le nombre d’opérations effectuées par
un algorithme, on fait recours donc à une approximation de ce nombre d’opérations
représentant ce qu’on appel ordre de grandeur de la complexité.

Définition 1
On dit que une fonction f est dominée par une fonction g si et seulement si :

∃n0 , c > 0 tq f (n) ≤ c.g(n) ∀n ≥ n0

On notera f = O(g) et on dit que f est du même ordre de grandeur que g

Complexité Algorithmique 16 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

Remarque 4
Si f = O(g) et g = O(h) alors f = O(h)
si f = O(g) et k une constante alors k ∗ f = O(g)
si f1 = O(g1 ) et f2 = O(g2 ) alors :
f1 + f2 = O(g1 + g2 )
f1 ∗ f2 = O(g1 ∗ g2 )

Complexité Algorithmique 17 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

Remarque 4
Si f = O(g) et g = O(h) alors f = O(h)
si f = O(g) et k une constante alors k ∗ f = O(g)
si f1 = O(g1 ) et f2 = O(g2 ) alors :
f1 + f2 = O(g1 + g2 )
f1 ∗ f2 = O(g1 ∗ g2 )

Règles de simplification :

Un nombre constant d’instructions est négligeable par rapport à la croissance de

la taille des données, ce qui permet d’annuler les constantes additives.
Pour de grandes valeurs de n, c’est bien sûr le terme de plus haut degré qui est
dominant
Les processeurs actuels effectuent plusieurs millions d’opérations par seconde, on
remplace donc les constantes multiplicatives par des 1.

Complexité Algorithmique 17 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

Exemple 7
f (n) = n3 + 2n2 + 4n + 2 = O(n3 ) (si n ≥ 1 alors f (n) ≤ 8n3 )
f (n) = nlog(n) + 12n + 888 = O(nlog(n))
2n
f (n) = 1000n1 0 − n7 + 12n4 + 1000 = O(2n )

Remarque : La complexité d’une instruction élémentaire est un O(1) : on dit qu’elle

s’effectue en temps constant

Complexité Algorithmique 18 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Classes de complexités les plus usuelles

Les algorithmes se regroupent en plusieurs familles, selon leurs complexités :

temps constant O(1) quelque soit la taille de l’entrée, le nombre

d’opérations effectuées est constant.
temps sous linéaire O(log(n)) Le temps présente une dépendance logarithmique
par rapport à la taille de l’entrée.
temps linéaire O(n) si la taille de l’entrée double, le temps double
temps quasi-linéaire O(nlog(n)) augmentation un peu supérieur à O(n)
temps quadratique O(n2 ) quand la taille de l’entrée double, le temps
d’exécution est multiplié par 4
temps polynomial O(nk ) quand la taille de l’entrée double, le temps
d’exécution est multiplié par 2k
temps exponentiel O(kn ) quand la taille de l’entrée double, le temps
d’exécution est élevé à la puissance 2
factorielle O(n!) asymptotiquement équivalente à nn

Complexité Algorithmique 19 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Classes de complexités les plus usuelles

Complexité Algorithmique 20 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

Exemple 8 (La fonction factorielle)

Complexité Algorithmique 21 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

Exemple 8 (La fonction factorielle)

def factorielle(n):
fact=1
for i in range(2,n+1):
fact=fact*i
return fact

Complexité Algorithmique 21 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

Exemple 8 (La fonction factorielle)

def factorielle(n):
fact=1
for i in range(2,n+1):
fact=fact*i
return fact

En fixant le i on exécute 2 opérations élémentaires (multiplication et affectation) ce

qui donne une complexité en O(n)
La boucle for va exécuter n − 1 fois (de i=2 jusqu’à n) un traitement de temps
constant, donc elle a une complexité : (n − 1) ∗ O(1) = O(n − 1) = O(n)
A l’extérieur de la boucle nous avons deux opérations élémentaires : return et
affectation qui s’exécutent en temps constant O(1)
La complexité est donc : O(n) + O(1) = O(n)

Complexité Algorithmique 21 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

Exemple 9 (vérifier si un tableau contient des doublons)

Complexité Algorithmique 22 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

Exemple 9 (vérifier si un tableau contient des doublons)

def sansDoublons(T) :
n= len(T)
for i in range (n-1) :
for j in range (i +1, n) :
if (T[i] = = T[j]) :
return False
return True

Complexité Algorithmique 22 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

Exemple 9 (vérifier si un tableau contient des doublons)

def sansDoublons(T) :
n= len(T)
for i in range (n-1) :
for j in range (i +1, n) :
if (T[i] = = T[j]) :
return False
return True

Dans le pire des cas le programme ne va pas trouver de doublons et retourne True,
donc il va comparer tous les éléments du tableau entre eux.

n−2 n−1 n−2 n−1

n(n − 1)
3+ ∑ ∑ 1 = 3+ ∑ (n − 1 − i) = 3 + ∑ i = 3 + 2
= O(n2 )
i=0 j=i+1 i=0 i=1

Dans le meilleur des cas les deux premiers éléments de T sont identiques (une
seule comparaison et un return) on aura donc une complexité constante O(1)

Complexité Algorithmique 22 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

Exemple 10 (produit matriciel)

Complexité Algorithmique 23 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

Exemple 10 (produit matriciel)

def ProduitMatriciel (A, B) :

n=len(A)
m= len(B[0])
p= len(B)
prod = [[0]*m for i in range(n) ]
for i in range(n) :
for j in range(m) :
s = 0
for k in range(p) :
s= s + A[i][k] * B[k][j]
prod[i][j]=s
return prod

Complexité Algorithmique 23 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

En effectue 3 affectations et 3 appels à la fonction len donc : coût= 6

Complexité Algorithmique 24 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

En effectue 3 affectations et 3 appels à la fonction len donc : coût= 6

Pour initialiser la matrice prod, en effectue n multiplications et une affectation ce
qui donne un coût= nm+1

Complexité Algorithmique 24 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

En effectue 3 affectations et 3 appels à la fonction len donc : coût= 6

Pour initialiser la matrice prod, en effectue n multiplications et une affectation ce
qui donne un coût= nm+1
Pour calculer une valeur de s : 3 opérations élémentaire (affectation, addition,
multiplication)

p−1
!!
n−1 m−1 n−1 m−1
C(n) = 6 + nm + 1 + ∑ ∑ 2+ ∑ 3 + 1 = 8 + nm + ∑ ∑ (2 + 3p)
i=0 j=0 k =0 i=0 j=0

= 8 + nm + nm(2 + 3p) = 8 + 3nm + 3npm = O(npm)

Complexité Algorithmique 24 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Notation O

En effectue 3 affectations et 3 appels à la fonction len donc : coût= 6

Pour initialiser la matrice prod, en effectue n multiplications et une affectation ce
qui donne un coût= nm+1
Pour calculer une valeur de s : 3 opérations élémentaire (affectation, addition,
multiplication)

p−1
!!
n−1 m−1 n−1 m−1
C(n) = 6 + nm + 1 + ∑ ∑ 2+ ∑ 3 + 1 = 8 + nm + ∑ ∑ (2 + 3p)
i=0 j=0 k =0 i=0 j=0

= 8 + nm + nm(2 + 3p) = 8 + 3nm + 3npm = O(npm)

Si les matrice A et B sont des matrices carrées alors n=m=p ce qui donne une
complexité en O(n3 )

Complexité Algorithmique 24 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Complexité des fonctions récursives

L’étude de la complexité d’un algorithme récursif consiste principalement à

déterminer le nombre d’appels récursifs en fonction de la taille des données d’entrée.
En règle générale, la complexité d’un algorithme récursif traitant des données d’une
certaine taille va dépendre de la complexité du même algorithme avec des données de
taille inférieure. Cette complexité va donc être une suite définie par récurrence

Complexité Algorithmique 25 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites arithmético-géométriques

Définition 2
Une suite réelle (Un )n∈N est dite arithmético-géométrique si :

∀a, b ∈ R tq ∀n ∈ N∗ Un = aUn−1 + b

Dans le contexte de calculs de complexité, a, b et U0 sont positifs, on a alors :

Si a = 1, alors : ∀n ∈ N Un = U0 + nb = O(n)
Si a > 1, on pose L = b
1−a , alors : ∀n ∈ N Un = (U0 − L)an + L = O(an )

Complexité Algorithmique 26 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites arithmético-géométriques
Exemple 11

def factorielle(n) :
if n<=1:
return 1
else :
return n*factorielle(n-1)

Complexité Algorithmique 27 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites arithmético-géométriques
Exemple 11

def factorielle(n) :
if n<=1:
return 1
else :
return n*factorielle(n-1)

Si n > 1, en effectue une comparaison lors du test, un produit et un appel récursif

sur une entrée de taille n-1.

Complexité Algorithmique 27 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites arithmético-géométriques
Exemple 11

def factorielle(n) :
if n<=1:
return 1
else :
return n*factorielle(n-1)

Si n > 1, en effectue une comparaison lors du test, un produit et un appel récursif

sur une entrée de taille n-1.
Si n ≤ 1, seule la comparaison a lieu.

Complexité Algorithmique 27 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites arithmético-géométriques
Exemple 11

def factorielle(n) :
if n<=1:
return 1
else :
return n*factorielle(n-1)

Si n > 1, en effectue une comparaison lors du test, un produit et un appel récursif

sur une entrée de taille n-1.
Si n ≤ 1, seule la comparaison a lieu.
La complexité est donc une suite arithmético-géométrique associée aux constantes
a = 1 et b = 2 :
C(n) = C(n − 1) + 2 pour n > 1 et C(0) = C(1) = 1

Complexité Algorithmique 27 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites arithmético-géométriques
Exemple 11

def factorielle(n) :
if n<=1:
return 1
else :
return n*factorielle(n-1)

Si n > 1, en effectue une comparaison lors du test, un produit et un appel récursif

sur une entrée de taille n-1.
Si n ≤ 1, seule la comparaison a lieu.
La complexité est donc une suite arithmético-géométrique associée aux constantes
a = 1 et b = 2 :
C(n) = C(n − 1) + 2 pour n > 1 et C(0) = C(1) = 1

Cet algorithme est donc de complexité linéaire :

C(n) = C(1) + (n − 1)b = 1 + 2(n − 1) = 2n − 1 = O(n)

Complexité Algorithmique 27 / 40
 Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites récurrentes linéaires

Définition 3 (Suites homogènes)

Une suite réelle (Un )n∈N est récurrente linéaire homogène d’ordre deux si :

∃a, b ∈ R tq ∀n ≥ 2, Un = aUn−1 + bUn−2

Pour étudier une telle suite, on lui associer un polynôme caractéristique : X2 − aX − b

Complexité Algorithmique 28 / 40
 Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites récurrentes linéaires

Définition 3 (Suites homogènes)

Une suite réelle (Un )n∈N est récurrente linéaire homogène d’ordre deux si :

∃a, b ∈ R tq ∀n ≥ 2, Un = aUn−1 + bUn−2

Pour étudier une telle suite, on lui associer un polynôme caractéristique : X2 − aX − b

Soit ∆ le discriminant de l’équation caractéristique associée X2 − aX − b = 0 :

Si ∆ > 0, soit X1 et X2 les deux racines avec X1 > 1 et |X1 | > |X2 | alors :

∃λ, µ ∈ R, ∀n ∈ N, Un = λX1n + µX2n = O(X1n )

si ∆ = 0 et X la racine réelle double :

∃λ, µ ∈ R, ∀n ∈ N, Un = (λn + µ)Xn = O(Xn )

Les constantes λ et µ se déterminent à l’aide des valeurs des deux premiers termes de
la suite.

Complexité Algorithmique 28 / 40
 Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites récurrentes linéaires

Définition 4 (Suites non homogènes)

Une suite réelle (Un )n∈N est récurrente linéaire non homogène d’ordre deux s’il existe deux
réels a et b et une fonction f de N dans R, tels que :

∀n ≥ 2, Un = aUn−1 + bUn−2 + f (n)

Le principe de résolution consiste à éliminer d’abord la fonction f (n), et ensuite

résoudre l’équation homogène ainsi trouvée.

Complexité Algorithmique 29 / 40
 Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites récurrentes linéaires

Exemple 12 (suite de Fibonacci)

def fibo(n):
if n<2:
return n
else :
return fibo(n-1)+fibo(n-2)

Complexité Algorithmique 30 / 40
 Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites récurrentes linéaires

Exemple 12 (suite de Fibonacci)

def fibo(n):
if n<2:
return n
else :
return fibo(n-1)+fibo(n-2)

Si n > 2, on effectue une comparaison et une addition entre deux appels récursifs. Si
n = 0 ou n = 1, seule la comparaison a [Link] a ainsi :

C(n − 1) + C(n − 2) + 2 si n ≥ 2
C(n) = (1)
1 sinon

Complexité Algorithmique 30 / 40
 Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites récurrentes linéaires

Exemple 12 (suite de Fibonacci)

def fibo(n):
if n<2:
return n
else :
return fibo(n-1)+fibo(n-2)

Si n > 2, on effectue une comparaison et une addition entre deux appels récursifs. Si
n = 0 ou n = 1, seule la comparaison a [Link] a ainsi :

C(n − 1) + C(n − 2) + 2 si n ≥ 2
C(n) = (1)
1 sinon

La complexité est donc une suite récurrente linéaire non homogène d’ordre deux. Cette
récurrence est aussi vraie pour n + 1 :

C(n) + C(n − 1) + 2 si n ≥ 2
C(n + 1) = (2)
1 sinon

Complexité Algorithmique 30 / 40
 Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites récurrentes linéaires

En soustrayant (1) de (2), on obtient l’équation suivante :

C(n + 1) − 2C(n) + C(n − 2) = 0

Complexité Algorithmique 31 / 40
 Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites récurrentes linéaires

En soustrayant (1) de (2), on obtient l’équation suivante :

C(n + 1) − 2C(n) + C(n − 2) = 0

Cette nouvelle équation est une équation homogène dont l’équation caractéristique
est :
X3 − 2X2 + 1 = (X − 1)(X2 − X − 1) = 0

Complexité Algorithmique 31 / 40
 Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites récurrentes linéaires

En soustrayant (1) de (2), on obtient l’équation suivante :

C(n + 1) − 2C(n) + C(n − 2) = 0

Cette nouvelle équation est une équation homogène dont l’équation caractéristique
est :
X3 − 2X2 + 1 = (X − 1)(X2 − X − 1) = 0
et dont les racines sont :
√ √
1+ 5 1− 5
X1 = et X2 = et X3 = 1
2 2

Complexité Algorithmique 31 / 40
 Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites récurrentes linéaires

En soustrayant (1) de (2), on obtient l’équation suivante :

C(n + 1) − 2C(n) + C(n − 2) = 0

Cette nouvelle équation est une équation homogène dont l’équation caractéristique
est :
X3 − 2X2 + 1 = (X − 1)(X2 − X − 1) = 0
et dont les racines sont :
√ √
1+ 5 1− 5
X1 = et X2 = et X3 = 1
2 2
√ !n √ !n √ !n !
1+ 5 1− 5 1+ 5
∃µ, λ, γ ∈ R, C(n) = λ +µ +γ = O
2 2 2

Complexité Algorithmique 31 / 40
 Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Récursivités simples

Suites récurrentes linéaires

En soustrayant (1) de (2), on obtient l’équation suivante :

C(n + 1) − 2C(n) + C(n − 2) = 0

Cette nouvelle équation est une équation homogène dont l’équation caractéristique
est :
X3 − 2X2 + 1 = (X − 1)(X2 − X − 1) = 0
et dont les racines sont :
√ √
1+ 5 1− 5
X1 = et X2 = et X3 = 1
2 2
√ !n √ !n √ !n !
1+ 5 1− 5 1+ 5
∃µ, λ, γ ∈ R, C(n) = λ +µ +γ = O
2 2 2

On détermine alors λ, µ et γ en se servant de la valeur des trois premiers termes

C(0) = 1 et C(1) = 1 et C(2) = 4.
La complexité de cet algorithme est donc exponentielle.

Complexité Algorithmique 31 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Suites non-linéaires de type "diviser pour régner"

Suites non-linéaires de type "diviser pour régner"

Principe
La méthode de diviser pour régner est une méthode qui permet, parfois de trouver des
solutions efficaces à des problèmes algorithmiques. Elle se fait en trois étapes :
Diviser : on divise les données initiales en plusieurs sous-parties.
Régner : on résout récursivement chacun des sous problèmes associés (ou on les
résout directement si leur taille est assez petite).
Combiner : combiner les différents résultats obtenus pour obtenir une solution au
problème initial.

Complexité Algorithmique 32 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Suites non-linéaires de type "diviser pour régner"

Suites non-linéaires de type "diviser pour régner"

Avec ce paradigme, la complexité d’un algorithme traitant des données de taille n

s’écrit souvent :
C(n) = aC( nb ) + f (n)

C(n0 ) = c

n est la taille du problème initial

a est le nombre de sous-problèmes
n
b la taille de chaque sous problème
f (n) est le coût de la subdivision et de la combinaison des solutions des
sous-problèmes.

Complexité Algorithmique 33 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Suites non-linéaires de type "diviser pour régner"

Suites non-linéaires de type "diviser pour régner"

Théorme génerale
Soit C(n) une fonction définie par l’équation de récurrence suivante :
n
T (n) = aT ( ) + O(nk )
b

Si a > bk alors C(n) = O(nlogb (a) )

Si a = bk alors C(n) = O(nk logb (n))
Si a < bk alors C(n) = O(nk )

Complexité Algorithmique 34 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Suites non-linéaires de type "diviser pour régner"

Suites non-linéaires de type "diviser pour régner"

Exemple 13 (Recherche Dichotomique récursive)

def dicho(l, x, d, f):

if d > f:
return False
else:
m = (d + f) // 2
if l[m] = = x:
return True
elif x < l[m]:
return dicho(l,x,d,m-1)
else:
return dicho(l,x,m+1,f)

Complexité Algorithmique 35 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Suites non-linéaires de type "diviser pour régner"

Suites non-linéaires de type "diviser pour régner"

Exemple 13 (Recherche Dichotomique récursive)

def dicho(l, x, d, f):

if d > f:
return False
else:
m = (d + f) // 2
if l[m] = = x:
return True
elif x < l[m]:
return dicho(l,x,d,m-1)
else:
return dicho(l,x,m+1,f)

On a :
n
T (n) = O(1) + T ( ) et T (0) = O(1)
2
On a : a = 1 et b = 2, f (n) = O(1) donc k = 0 et a = bk = 1
D’où d’après le théorème général : T (n) = O(log2 (n))

Complexité Algorithmique 35 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Résolution par substitution répétitive

Résolution par substitution répétitive

Une autre façon de résoudre une équation de récurrence est de substituer, de façon
répétitive, la définition de la fonction dans le coté droit de son équation jusqu’à ce
qu’une forme simple soit obtenue.

Exemple 14

T (n − 1) + 2 si n > 1
T (n) =
1 sinon

Complexité Algorithmique 36 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Résolution par substitution répétitive

Résolution par substitution répétitive

Une autre façon de résoudre une équation de récurrence est de substituer, de façon
répétitive, la définition de la fonction dans le coté droit de son équation jusqu’à ce
qu’une forme simple soit obtenue.

Exemple 14

T (n − 1) + 2 si n > 1
T (n) =
1 sinon

En substituant à chaque fois dans la récurrence on obtient : T (n) = T (n − 1) + 2

= (T (n − 2) + 2) + 2
..
.
= 1 + ∑ni=−11 2
= 1 + 2(n − 1)
= O(n)

Complexité Algorithmique 36 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Résolution par substitution répétitive

Résolution par substitution répétitive

Exemple 15

T (n − 1) + n si n > 1
T (n) =
1 si n = 1

Complexité Algorithmique 37 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Résolution par substitution répétitive

Résolution par substitution répétitive

Exemple 15

T (n − 1) + n si n > 1
T (n) =
1 si n = 1

En substituant à chaque fois dans la récurrence on obtient :

T (n) = T (n − 1) + n
= (T (n − 2) + (n − 1)) + n
.
..
= T (1) + 2 + · + (n − 1) + n = 1 + 2 + · + (n − 1) + n = ∑ni=1 i
= n(n2−1)
= O(n2 )

Complexité Algorithmique 37 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Résolution par substitution répétitive

Résolution par substitution répétitive

Exemple 16

2T ( n2 ) + n

si n > 1
T (n) =
1 si n = 1

Complexité Algorithmique 38 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Résolution par substitution répétitive

Résolution par substitution répétitive

Exemple 16

2T ( n2 ) + n

si n > 1
T (n) =
1 si n = 1

Donc T ( n2 ) = 2T ( 2n2 ) + n2 On substituant d’une façon répétitive jusqu’à arriver au cas

de baseT (1), c’est-à-dire à une étape k qui vérifie 2nk = 1 donc à l’étape k = log2 (n) :
T (n) = 2T ( n2 ) + n
= 2(2T ( 2n2 ) + n2 ) + n
= 2n + 22 T ( 2n2 )
.
..
 
= (k − 1)n + 2k−1 2kn−1 + 2T ( 2nk )
= kn + 2k T ( 2nk )
= nlog2 (n) + 2log2 (n) T (1)
= nlog2 (n) + n = O(nlog2 (n))

Complexité Algorithmique 38 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Résolution par induction

Résolution par induction

Cette méthode consiste à deviner la solution, et puis de la démontrer à l’aide du

principe de récurrence.

Exemple 17

C( n2 ) + 1

si n > 1
C(n) =
1 si n = 1
Montrons que : C(n) = 1 + log2 (n)

Complexité Algorithmique 39 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

Résolution par induction

Résolution par induction

Cette méthode consiste à deviner la solution, et puis de la démontrer à l’aide du

principe de récurrence.

Exemple 17

C( n2 ) + 1

si n > 1
C(n) =
1 si n = 1
Montrons que : C(n) = 1 + log2 (n)

cas de base : pour n = 1

C(1) = 1 + log2 (1) = 1, donc le cas de base est bien vérifié pour n = 1.
supposons que la propriété est vrais pour tous k < n et montrons qu’elle est vrai pour
n + 1.
Récurrence :
C(n) = C( n2 ) + 1 = 1 + log2 ( n2 ) + 1 = 2 + log2 (n) − log2 (1) = 1 + log2 (n) Donc on a
pour tous n > 1C(n) = 1 + log2 (n)

Complexité Algorithmique 39 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

complexité spatiale

De la même façon qu’on définit la complexité temporelle d’un algorithme pour évaluer
ses performances en temps de calcul, on peut définir sa complexité spatiale pour
évaluer sa consommation en espace mémoire. Le principe est le même sauf qu’ici on
cherche à évaluer l’ordre de grandeur du volume en mémoire utilisé : il ne s’agit pas
d’évaluer précisément combien d’octets sont consommés par un algorithme mais de
préciser son taux de croissance (ordre de grandeur) en fonction de la taille de l’entrée.

Complexité Algorithmique 40 / 40
Introduction Calcul du coût d’un algorithme Type de complexité Complexité asymptotique Complexité des fonctions récursives complexité spatiale

complexité spatiale

De la même façon qu’on définit la complexité temporelle d’un algorithme pour évaluer
ses performances en temps de calcul, on peut définir sa complexité spatiale pour
évaluer sa consommation en espace mémoire. Le principe est le même sauf qu’ici on
cherche à évaluer l’ordre de grandeur du volume en mémoire utilisé : il ne s’agit pas
d’évaluer précisément combien d’octets sont consommés par un algorithme mais de
préciser son taux de croissance (ordre de grandeur) en fonction de la taille de l’entrée.
les variables simples (entiers, booléens, flottants) occupent un espace constant
O(1) qui ne dépend pas de l’entrée.
La taille d’un tableau est en grand O du produit de ces dimensions :
Un tableau à une dimension de N éléments est en O(N ).
une matrice NxM est en O(MN )
Les chaînes de caractères sont en grand O de leur longueur.

Complexité Algorithmique 40 / 40