Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité

té spatiale

Complexité Algorithmique
Filière : MP

EL BOUNI FATIMA-ZAHRA

elbouni97@[Link]
Classes préparatoires aux grandes écoles
Lycée Moulay Ali Cherif-ERRACHIDIA

September 21, 2024

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 1 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

1 Introduction

2 Notion de complexité

3 Complexité et Notations asymptotiques

4 Analyse de complexité des algorithmes

5 Complexité d’un algorithme récursif

6 Complexité spatiale

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 2 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

1 Introduction

2 Notion de complexité

3 Complexité et Notations asymptotiques

4 Analyse de complexité des algorithmes

5 Complexité d’un algorithme récursif

6 Complexité spatiale

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 3 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Introduction

Comment peut-on définir un algorithme ?

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 4 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Introduction

Comment peut-on définir un algorithme ?

Proposer un algorithme qui détermine l’existence d’occurrence d’une lettre dans

une chaîne de caractère.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 4 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Introduction

Comment peut-on définir un algorithme ?

Proposer un algorithme qui détermine l’existence d’occurrence d’une lettre dans

une chaîne de caractère.

Comment peut-on désigner le meilleur algorithme(solution) parmi les algorithmes

proposés.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 4 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Introduction

Comment peut-on définir un algorithme ?

Proposer un algorithme qui détermine l’existence d’occurrence d’une lettre dans

une chaîne de caractère.

Comment peut-on désigner le meilleur algorithme(solution) parmi les algorithmes

proposés.

La réponse intuitive : est de mesurer le temps d’exécution relatif à chaque

algorithme en utilisant le module time de Python et de comparer les résultats.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 4 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Problématique

Cette solution n’est pas bien applicable en réalité car on ne sait pas le
comportement de n’importe algorithme quand leurs paramètres d’entrées deviens
assez grands.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 5 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

1 Introduction

2 Notion de complexité

3 Complexité et Notations asymptotiques

4 Analyse de complexité des algorithmes

5 Complexité d’un algorithme récursif

6 Complexité spatiale

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 6 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Notion de complexité

Définition
Pour un même problème P, on peut trouver plusieurs algorithmes (Alg1 , Alg2 , ..., Algn ), la
complexité d’un problème mesure la quantité des ressources nécessaires à la résolution
du problème P.
Cette mesure représente une estimation d’opérations de base en fonction de la taille
des données.

Remarques
L’objectif de la complexité consiste à évaluer le coût d’exécution de chaque
algorithme afin de choisir le meilleur;
Dans un ordinateur, on distingue deux types de ressources : la vitesse d’exécution
du microprocesseur, et le nombre de cases de la mémoire centrale (RAM).

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 7 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Types de complexité

En fonction des ressources utilisées, on sera amené à distinguer deux types de

complexité :
1 La complexité temporelle (en temps) : est le nombre d’opérations élémentaires
(affectations, comparaisons, opérations arithmétiques) effectuées par un
programme;
2 La complexité spatiale (en espace) : consiste à estimer le nombre
d’emplacements mémoires occupés lors de l’exécution d’un programme.
Alors le temps d’exécution et l’espace mémoire présentent le coût d’exécution d’un
programme donné.

Remarque
Dans ce cours, on s’intéressera le plus souvent à la complexité temporelle.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 8 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Différentes nuances de complexité

Soient Dn l’ensemble de données de taille n et C(d) est le coût d’exécution de

l’algorithme sur la donnée de taille n.

La complexité dans le pire des cas

Est le plus grand nombre d’opérations qu’aura à exécuter l’algorithme sur un jeu de
données de taille fixée à n.
Tpire (n) = Max(C(d)d∈Dn )

La complexité en moyenne des cas

On calcul le coût pour chaque donnée possible puis on divise la somme de ces coûts par
le nombre de données différentes:

1Xn
Tmoyenne (n) = C(d)d∈Dn
n

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 9 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Différentes nuances de complexité

La complexité dans le meilleur des cas

Est le plus petit nombre d’opérations qu’aura à exécuter l’algorithme pour des données
de taille n.
Tmeilleur (n) = Min(C(d)d∈Dn )

Remarque
En analyse de complexité, on étudie souvent le pire des cas ce qui donne une borne
supérieure de la complexité de l’algorithme.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 10 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

1 Introduction

2 Notion de complexité

3 Complexité et Notations asymptotiques

4 Analyse de complexité des algorithmes

5 Complexité d’un algorithme récursif

6 Complexité spatiale

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 11 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Complexité et Notations asymptotiques

Plusieurs facteurs influencent le temps d’exécution d’un programme. On ne peut pas

déterminer le temps d’exécution d’une façon exacte.
Parmi ces facteurs qui interviennent dans le temps d’exécution, nous citons :
La machine qui l’exécute;
Le système d’exploitation installé;
Le langage dans lequel li est écrit;
Le style de la programmation utilisé;
Les données d’entrée sont de grandes tailles;
Etc.
Afin de surmonter ce problème, nous introduisons le concept de notation
asymptotique. Cette notation a pour but d’estimer le temps d’exécution d’un
programme.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 12 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Notations de Landau

Soit f (n) une fonction qui désigne le temps de calcul d’un algorithme A.
Notation O
On dit que f (n) est en grand O de g(n) si et seulement si :

∃(n0 , c); f (n) ≤ c.g(n); ∀n ≥ n0

On note : f (n) = O (g(n)).

Figure 1: g(n) est borne supérieure asymptotique pour f (n)

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 13 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Notations de Landau

Notation Ω
On dit que f (n) est en grand Ω de g(n) :

∃(n0 , c); f (n) ≥ c.g(n); ∀n ≥ n0

On note : f (n) = Ω(g(n)).

Figure 2: g(n) est borne inférieure asymptotique pour f (n)

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 14 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Notations de Landau

Notation Θ
On dit que f (n) est en grand Θ de g(n) :

∃(n0 , c1 , c2 ); c1 .g(n) ≤ f (n) ≤ c2 .g(n); ∀n ≥ n0

On note : f (n) = Θ(g(n)).

Figure 3: g(n) est borne asymptotique pour f (n)

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 15 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Classes de complexité les plus usuelles

Complexité Nom Description Exemples

O (1) Constante Le temps d’exécution ne dépend pas des données Addition, Comparaison, Affectation...
traitées, ce qui est assez rare!

O (log(n)) Logarithmique augmentation très faible du temps d’exécution Recherche dichotomique

quand le paramètre croit

O (n) Linéaire Augmentation linéaire du temps d’exécution quan- Calcul de produit scalaire de deux
dle paramètre croit. vecteurs de R...

O (nlog(n)) Quasi-linéaire Augmentation un peu supérieure à O (n) Tri rapide, Tri fusion ...

O (n2 ) Quadratique La complexité est liée au carré du nombre d’entrées. Tri sélection,boucles imbriquées...

O (nk ) Polynomiale nk est le terme de plus haut degré d’un polynôme Multiplication de deux matrices car-
en n; il n’est pas rare de voir des complexités en rées d’ordre n
O (n3 ) ouO(n4 ).

O (an ) Exponentielle Quand le paramètre double, le temps d’exécution Tours de Hanoï

est élevé à la puissance k avec k≥ 1

O (n!) Factorielle Asymptotique-ment équivalente à nn Permutations d’un ensemble

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 16 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Classes de complexité les plus usuelles

Figure 4: Classes de complexité usuelles

O (1) ⊆ O (log(n)) ⊆ O (n) ⊆ O (nlog(n)) ⊆ O (n2 ) ⊆ O (nk ) ⊆ O (an ) ⊆ O (n!)

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 17 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Comparaison de temps d’exécution

Avec un ordinateur capable d’accomplir 108 opérations par seconde

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 18 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

1 Introduction

2 Notion de complexité

3 Complexité et Notations asymptotiques

4 Analyse de complexité des algorithmes

5 Complexité d’un algorithme récursif

6 Complexité spatiale

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 19 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Évaluer la complexité d’un algorithme

L’évaluation de la complexité d’un algorithme repose sur la mesure du temps

d’exécution (TE), qui dépend du coût des instructions élémentaires (IE)et des
instructions composées (IC) .
Instructions élémentaires (IE) : Ce sont des instructions de base qui prennent un
temps fixe pour être exécutées, indépendamment de la taille des données
d’entré[Link] instruction élémentaire peut être:
Une affectation;
Un test de comparaison :==, <, <=, >=,! =;
Une opération de lecture (input) et écriture (print) ;
Une opération arithmétique :+, .-*,/;
Accès à un élément d’un tableau (en supposant que l’accès se fait en temps constant).
Le coût des instructions élémentaires est généralement considéré comme une
constante (disons O (1)) dans l’évaluation de la complexité.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 20 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Évaluer la complexité d’un algorithme

Instructions composées (IC) : Ce sont des blocs d’instructions qui peuvent

dépendre de la taille de l’entrée et peuvent impliquer des boucles, des conditions,
ou des appels à d’autres fonctions.
Le coût d’une instruction conditionnelle f du type if b: Q1 else: Q2 est
C(f ) = C(test) + max(C(Q1), C(Q2))
Le coût d’une boucle for est obtenu par le calcul de coût de:
Une initialisation qui s’exécute une seule fois;
Chaque étape de la boucle on fait deux instructions : une instruction pour incrémenter le
compteur et une instruction pour comparer le compteur avec la valeur finale de la boucle
P
C(f ) = 1 + (2 + C(xi ))
Le coût d’une boucle while est
P
C(f ) = (C(comparaison) + C(xi ))
avec C(xi ) représente le coût de chaque instruction (xi )du corps de la boucle.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 21 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Règles de calcul de complexité

Après avoir déterminer les coûts d’exécution des instructions élémentaires et des
instructions composées dans un algorithme on peut trouver la borne asymptotique
(notation O )en appliquant les règles suivantes:
1 Les constantes multiplicatives sont remplacées par 1.
2 Les constante additatives sont annulées.
3 Le terme le plus élevé est conservé.

Exemples
O (3n2 + 8n + 4) :

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 22 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Règles de calcul de complexité

Après avoir déterminer les coûts d’exécution des instructions élémentaires et des
instructions composées dans un algorithme on peut trouver la borne asymptotique
(notation O )en appliquant les règles suivantes:
1 Les constantes multiplicatives sont remplacées par 1.
2 Les constante additatives sont annulées.
3 Le terme le plus élevé est conservé.

Exemples
O (3n2 + 8n + 4) : O (n2 )

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 22 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Règles de calcul de complexité

Après avoir déterminer les coûts d’exécution des instructions élémentaires et des
instructions composées dans un algorithme on peut trouver la borne asymptotique
(notation O )en appliquant les règles suivantes:
1 Les constantes multiplicatives sont remplacées par 1.
2 Les constante additatives sont annulées.
3 Le terme le plus élevé est conservé.

Exemples
O (3n2 + 8n + 4) : O (n2 )
O (2n + 8n3 + 14n2 ) :

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 22 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Règles de calcul de complexité

Après avoir déterminer les coûts d’exécution des instructions élémentaires et des
instructions composées dans un algorithme on peut trouver la borne asymptotique
(notation O )en appliquant les règles suivantes:
1 Les constantes multiplicatives sont remplacées par 1.
2 Les constante additatives sont annulées.
3 Le terme le plus élevé est conservé.

Exemples
O (3n2 + 8n + 4) : O (n2 )
O (2n + 8n3 + 14n2 ) : O (2n )

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 22 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Règles de calcul de complexité

Après avoir déterminer les coûts d’exécution des instructions élémentaires et des
instructions composées dans un algorithme on peut trouver la borne asymptotique
(notation O )en appliquant les règles suivantes:
1 Les constantes multiplicatives sont remplacées par 1.
2 Les constante additatives sont annulées.
3 Le terme le plus élevé est conservé.

Exemples
O (3n2 + 8n + 4) : O (n2 )
O (2n + 8n3 + 14n2 ) : O (2n )
O (4n + 33log(n + 6)) :

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 22 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Règles de calcul de complexité

Après avoir déterminer les coûts d’exécution des instructions élémentaires et des
instructions composées dans un algorithme on peut trouver la borne asymptotique
(notation O )en appliquant les règles suivantes:
1 Les constantes multiplicatives sont remplacées par 1.
2 Les constante additatives sont annulées.
3 Le terme le plus élevé est conservé.

Exemples
O (3n2 + 8n + 4) : O (n2 )
O (2n + 8n3 + 14n2 ) : O (2n )
O (4n + 33log(n + 6)) : O (n)

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 22 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples de calcul de complexité

La complexité de l’algorithme Permutation qui fait l’échange deux entiers est

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 23 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples de calcul de complexité

La complexité de l’algorithme Permutation qui fait l’échange deux entiers est O (1).

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 23 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples de calcul de complexité

La complexité de l’algorithme Somme1 des n premiers entiers est alors

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 24 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples de calcul de complexité

La complexité de l’algorithme Somme1 des n premiers entiers est alors O (n).

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 24 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples de calcul de complexité

La complexité de l’algorithme estPremier1 qui teste si le nombre entier n est premier est

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 25 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples de calcul de complexité

La complexité de l’algorithme estPremier1 qui teste si le nombre entier n est premier est
O (n).
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 25 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples de calcul de complexité

La complexité de l’algorithme estPremier2 qui teste si le nombre entier n est premier est

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 26 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples de calcul de complexité

La complexité de l’algorithme estPremier2 qui teste si le nombre entier n est premier est
p
O ( n).
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 26 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples de calcul de complexité

La complexité de l’algorithme machin1 est

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 27 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples de calcul de complexité

La complexité de l’algorithme machin1 est O (n2 ).

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 27 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

1 Introduction

2 Notion de complexité

3 Complexité et Notations asymptotiques

4 Analyse de complexité des algorithmes

5 Complexité d’un algorithme récursif

6 Complexité spatiale

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 28 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Complexité des fonctions récursives

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

nombre d’appels récursifs en fonction de la taille des données d’entrée.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 29 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Complexité des fonctions récursives

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

nombre d’appels récursifs en fonction de la taille des données d’entrée.
En général, la complexité d’un tel algorithme dépend de la complexité du même
algorithme appliqué à des données de taille inférieure, ce qui se traduit par une
équation récurrente.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 29 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Complexité des fonctions récursives

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

nombre d’appels récursifs en fonction de la taille des données d’entrée.
En général, la complexité d’un tel algorithme dépend de la complexité du même
algorithme appliqué à des données de taille inférieure, ce qui se traduit par une
équation récurrente.
Pour déterminer la complexité temporelle, on exprime le coût de l’algorithme sous
forme d’équations récurrentes, puis on les résout pour obtenir une expression
asymptotique.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 29 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Complexité des fonctions récursives

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

nombre d’appels récursifs en fonction de la taille des données d’entrée.
En général, la complexité d’un tel algorithme dépend de la complexité du même
algorithme appliqué à des données de taille inférieure, ce qui se traduit par une
équation récurrente.
Pour déterminer la complexité temporelle, on exprime le coût de l’algorithme sous
forme d’équations récurrentes, puis on les résout pour obtenir une expression
asymptotique.
Les outils essentiels pour cette analyse incluent la technique de sommation, la
substitution répétitive et le théorème maître (Master Theorem).

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 29 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Technique de sommation

La technique de sommation est utilisée pour résoudre des équations récurrentes en les
exprimant sous forme de sommes, puis en résolvant ces sommes pour obtenir une
expression asymptotique de la complexité.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 30 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Technique de sommation

La technique de sommation est utilisée pour résoudre des équations récurrentes en les
exprimant sous forme de sommes, puis en résolvant ces sommes pour obtenir une
expression asymptotique de la complexité.

Principe
L’idée est de réécrire l’équation récurrente en une somme qui reflète le nombre
d’opérations effectuées à chaque étape de l’algorithme, puis de simplifier cette somme
pour obtenir une solution.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 30 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

Exemple 1 : La fonction factorielle

La factorielle n! est définie comme le produit de tous les entiers de 1 à n. L’equation
récurrente se traduite comme une suite arithmético-géométrique, car elle est le produit
d’une suite arithmétique (les entiers successifs) avec elle-même.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 31 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

Exemple 1 : La fonction factorielle

La factorielle n! est définie comme le produit de tous les entiers de 1 à n. L’equation
récurrente se traduite comme une suite arithmético-géométrique, car elle est le produit
d’une suite arithmétique (les entiers successifs) avec elle-même.

Définition
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)
b
Si a > 1, on pose L = 1−a , alors : ∀n ∈ N Un = (U0 − L)an + L = O (an )

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 31 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

1 def factorielle ( n ) :
2 if n <=1:
3 return 1
4 else :
5 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.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 32 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

1 def factorielle ( n ) :
2 if n <=1:
3 return 1
4 else :
5 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.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 32 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

1 def factorielle ( n ) :
2 if n <=1:
3 return 1
4 else :
5 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)

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 32 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

Exemple 2 : Suite de Fibonacci

La suite de Fibonacci est définie par :

F(n) = F(n − 1) + F(n − 2)

avec
F(0) = 0, F(1) = 1
L’equation récurrente se traduite comme une suite récurrente linéaire non homogène
d’ordre deux.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 33 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

Exemple 2 : Suite de Fibonacci

La suite de Fibonacci est définie par :

F(n) = F(n − 1) + F(n − 2)

avec
F(0) = 0, F(1) = 1
L’equation récurrente se traduite comme une suite récurrente linéaire non homogène
d’ordre deux.

Définition
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

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 33 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

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

Soit ∆ le discriminant de l’équation caractéristique associée X 2 − 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 + µ)X n = O (X n )

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

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 34 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

Définition
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.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 35 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

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

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 36 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

1 def fibo ( n ):
2 if n <2:
3 return n
4 else :
5 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

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 36 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

1 def fibo ( n ):
2 if n <2:
3 return n
4 else :
5 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
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 36 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

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

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

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 37 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

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:
X 3 − 2X 2 + 1 = (X − 1)(X 2 − X − 1) = 0

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 37 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

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:
X 3 − 2X 2 + 1 = (X − 1)(X 2 − X − 1) = 0
et dont les racines sont:
p p
1+ 5 1− 5
X1 = et X2 = et X3 = 1
2 2

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 37 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

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:
X 3 − 2X 2 + 1 = (X − 1)(X 2 − X − 1) = 0
et dont les racines sont:
p p
1+ 5 1− 5
X1 = et X2 = et X3 = 1
2 2
à p !n à p !n Ãà p !n !
1+ 5 1− 5 1+ 5
∃µ, λ, γ ∈ R, C(n) = λ +µ +γ = O
2 2 2

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 37 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemples

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:
X 3 − 2X 2 + 1 = (X − 1)(X 2 − X − 1) = 0
et dont les racines sont:
p p
1+ 5 1− 5
X1 = et X2 = et X3 = 1
2 2
à p !n à p !n Ãà p !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.
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 37 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

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.
½
T (n − 1) + 2 si n > 1
T (n) =
1 sinon

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 38 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

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.
½
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 + n−1
P
= i=1 2
= 1+2(n-1)
= O (n)

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 38 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Résolution par substitution répétitive

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

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 39 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Résolution par substitution répétitive

½
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
Pn
= i=1 i
n(n−1)
= 2
2
= O (n )

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 39 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Résolution par substitution répétitive

2T ( n2 ) + n si n > 1
½
T (n) =
1 si n = 1

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 40 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Résolution par substitution répétitive

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
base T (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 )
..
. ³ ´
n
= (k − 1)n + 2k−1 2k−1
+ 2T ( 2nk )
= kn + 2k T ( 2nk )
= nlog2 (n) + 2log2 (n) T (1)
= nlog2 (n) + n
= O (nlog2 (n))
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 40 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Résolution par induction

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

principe de récurrence.
C( n2 ) + 1 si n > 1
½
C(n) =
1 si n = 1
Montrons que : C(n) = 1 + log2 (n)

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 41 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Résolution par induction

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

principe de récurrence.
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 (2) = 1 + log2 (n)
Donc on a pour tous n>1 : C(n) = 1 + log2 (n)

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 41 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Le théorème maître

Le théorème maître (Master Theorem) est une méthode puissante et directe pour
résoudre certaines équations récurrentes en se basant sur le principe 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.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 42 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Le théorème maître

Avec ce paradigme, la complexité d’un algorithme traitant des données de taille n s’écrit
souvent :
T (n) = aT ( nb ) + f (n)
½

T (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.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 43 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Le théorème maître

Théorème Générale(Master Theorem)

Soit T (n) une fonction définie par l’équation de récurrence suivante :
n
T (n) = aT ( ) + [Link]
b

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

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

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 44 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemple

1 def dicho (l , x , d , f ):
2 if d > f :
3 return False
4 else :
5 m = ( d + f ) // 2
6 if l [ m ] = = x :
7 return True
8 elif x < l [ m ]:
9 return dicho (l ,x ,d ,m -1)
10 else :
11 return dicho (l ,x , m +1 , f )

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 45 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

Exemple

1 def dicho (l , x , d , f ):
2 if d > f :
3 return False
4 else :
5 m = ( d + f ) // 2
6 if l [ m ] = = x :
7 return True
8 elif x < l [ m ]:
9 return dicho (l ,x ,d ,m -1)
10 else :
11 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))
EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 45 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif Complexité spatiale

1 Introduction

2 Notion de complexité

3 Complexité et Notations asymptotiques

4 Analyse de complexité des algorithmes

5 Complexité d’un algorithme récursif

6 Complexité spatiale

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 46 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif 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.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 47 / 47
Introduction Notion de complexité Complexité et Notations asymptotiques Analyse de complexité des algorithmes Complexité d’un algorithme récursif 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 N × M est en O (MN)
Les chaînes de caractères sont en grand O de leur longueur.

EL BOUNI F-Z (CPGE-Moulay Ali Cherif ) Complexité Algorithmique September 21, 2024 47 / 47