2
Complexité algorithmique
Structures de données avancées -----------------------------------------Pr. EL KASMI
1. Notion de complexité
3
Introduction
Structures de données avancées -----------------------------------------Pr. EL KASMI
1. Notion de complexité
4
Introduction
Structures de données avancées -----------------------------------------Pr. EL KASMI
1. Notion de complexité
5
Types de complexité
Structures de données avancées -----------------------------------------Pr. EL KASMI
1. Notion de complexité
6 Exemple
Procedure Mystere1(n: Entier)
Début
Pour i allant de 1 à n
Si n mod i == 0 alors
Ecrire(i)
FinSi
FinPour
Fin
Analyse:
Cette procédure réalise exactement :
✓n calculs de reste de divisions euclidiennes
✓n comparaisons
✓et au plus n affichages.
Structures de données avancées -----------------------------------------Pr. EL KASMI
1. Notion de complexité
7 Exemple
Function Mystere2(n: Entier)
Début
Pour i allant de 1 à n
Si n mod i == 0 alors
Retourner (i)
FinSi
FinPour
Fin
Analyse:
Cette fonction réalise exactement :
✓Un seul calcul de reste de division euclidienne
✓Une seule comparaison
✓Une seule opération de retournement du résultat.
Structures de données avancées -----------------------------------------Pr. EL KASMI
2. Complexité et notation de grand o (O)
8
En réalité, lorsqu’on cherche à évaluer l’efficacité d’un
algorithme, il est souvent inutile d’aller jusqu’à ce
niveau de détail : on se contentera de dire que le
nombre d’opérations élémentaires effectuées est par
exemple proportionnel à n ou à n2, log(n),….
Structures de données avancées -----------------------------------------Pr. EL KASMI
2. Complexité et notation de grand o (O)
9
Pourquoi une notation asymptotique?
Structures de données avancées -----------------------------------------Pr. EL KASMI
2. Complexité et notation de grand o (O)
10
Structures de données avancées -----------------------------------------Pr. EL KASMI
2. Complexité et notation de grand o (O)
11
Structures de données avancées -----------------------------------------Pr. EL KASMI
2. Complexité et notation de grand o (O)
12
Structures de données avancées -----------------------------------------Pr. EL KASMI
3. Règles de calcul de la complexité d’un algorithme
13
Règle 1 : règle générale
La complexité d’un ensemble d’instructions est la somme des
complexités de chacune d’elles.
Structures de données avancées -----------------------------------------Pr. EL KASMI
3. Règles de calcul de la complexité d’un algorithme
14
Règle 2 : les instructions élémentaires
Les opérations élémentaires telle que l’affectation, test, opérations
logiques et arithmétiques, lecture et écriture d’une variable simple
…etc, sont en O(1) (complexité constante).
Structures de données avancées -----------------------------------------Pr. EL KASMI
3. Règles de calcul de la complexité d’un algorithme
15
Règle 3 : les instructions conditionnelles
Le coût d’une structure sélective
Si Condition alors :
Bloc A
Sinon
Bloc B
FinSi
Est inférieur ou égal au maximum des coûts des instructions A et B, plus le
temps d’évaluation de la condition.
Structures de données avancées -----------------------------------------Pr. EL KASMI
3. Règles de calcul de la complexité d’un algorithme
16
Règle 4 : les instructions de répétition
Le coût d’une boucle
Pour i allant de ValInitiale A ValFinale :
Bloc A
FinPour
✓ Est égal au nombre d’éléments de l’itérable multiplié par le coût du bloc A si ce
dernier ne dépend pas de la valeur de i.
✓ Quand le coût du corps de la boucle dépend de la valeur de i, le coût total de la
boucle est la somme des coûts du corps de la boucle pour chaque valeur de i.
Structures de données avancées -----------------------------------------Pr. EL KASMI
3. Règles de calcul de la complexité d’un algorithme
17
Règle 5 : les procédures et les fonctions
Leurs complexités sont déterminées par celle de leurs corps. L’appel à une
fonction est supposé prendre un temps constant en O(1).
La distinction entre les fonctions récursives et celles qui ne le sont pas. Dans le
cas de la récursivité, le temps de calcul est exprimé comme une relation de
récurrence.
Structures de données avancées -----------------------------------------Pr. EL KASMI
4. Les complexités les plus utilisées sont :
18
✓Complexité constante O(1) : On rencontre cette complexité quand toutes
les instructions du problème sont exécutées une seule fois quel que soit la
taille du problème.
✓Complexité linéaire O(n) : C’est le cas d’une boucle de 1 à n et le corps de
la boucle effectue un travail de durée constante et indépendante de n.
Exemple: Calcul du produit scalaire de deux vecteurs, somme des éléments
d’une liste, maximum d’une liste, …
Structures de données avancées -----------------------------------------Pr. EL KASMI
4. Les complexités les plus utilisées sont :
19
✓Complexité logarithmique O(log(n)) : La durée d’exécution croit
légèrement avec n. Ce cas se rencontre quand la taille du problème est
divisée ou multipliée par une constante à chaque itération.
Exemple : Recherche dichotomique dans une liste triée.
Structures de données avancées -----------------------------------------Pr. EL KASMI
4. Les complexités les plus utilisées sont :
20
✓Complexité quasi-linéaire ou n-logarithmique O(nlog(n)): se rencontre
dans les algorithmes où à chaque itération, la taille du problème est divisée par
une constante avec à chaque fois un parcours linéaire des données.
Exemple: Tri par fusion.
Structures de données avancées -----------------------------------------Pr. EL KASMI
4. Les complexités les plus utilisées sont :
21
✓Complexité quadratique O(n2) : C’est le cas des algorithmes avec deux
boucles imbriquées chacune allant de 1 à n et avec le corps de la boucle
interne qui est constant.
Exemple: Somme de deux matrices carrées d'ordre n, Tri à bulle, tri par
insertion, tri par sélection, …
Structures de données avancées -----------------------------------------Pr. EL KASMI
4. Les complexités les plus utilisées sont :
22
✓Complexité cubique O(n3) : généralement avec trois boucles imbriquées.
Exemple: Produit de deux matrices carrées d'ordre n
Complexité exponentielle O(2n) : Les algorithmes de ce genre sont dits naïfs
car ils sont inefficaces et inutilisables dès que n dépasse 50. On rencontre
typiquement ces algorithmes dans les parcours arborescents.
Exemple: Tours de Hanoï.
Structures de données avancées -----------------------------------------Pr. EL KASMI
4. Les complexités les plus utilisées sont :
23
Structures de données avancées -----------------------------------------Pr. EL KASMI
5. Comparaison du temps d’exécution
24
Prenons trois ordinateurs, dont la vitesse du microprocesseur varie entre
106 HZ et 1012 HZ et imaginons des algorithmes qui effectuent un
traitement donné dans un temps T(N).
Nous donnons ci-dessous tableau des ordres de grandeur des temps
d’exécution que l’on peut espérer pour des données de taille 106 suivant la
complexité de l’algorithme.
Structures de données avancées -----------------------------------------Pr. EL KASMI
6. TD
25
TD
Structures de données avancées -----------------------------------------Pr. EL KASMI