22/02/20
Programmation avancée
Complexité algorithmique
EL Moukhtar ZEMMOURI
ENSAM – Meknès
Version – 1.0
Analyse des algorithmes
E. Zemmouri, ENSAM - Meknès 2
22/02/20
Analyse des algorithmes
• Analyser un algorithme : évaluer les ressources nécessaires à l’exécution
de cet algorithme.
o Le processeur (temps d’exécution)
o La mémoire
o …
• En général, en analysant plusieurs algorithmes susceptibles de résoudre le
même problème, on arrive à identifier le plus efficace.
• L’analyse du temps d’exécution est le plus important.
E. Zemmouri, ENSAM - Meknès 3
Analyse des algorithmes
• Analyse du temps d’exécution
o è complexité temporelle
• Analyse de l’espace mémoire
o è complexité spatiale
E. Zemmouri, ENSAM - Meknès 4
22/02/20
14 M o d è l e d e c a l c u l2 (• m a c h pas
Premiers ine)
• On suppose un modèle d’ordinateur! à !processeur unique capable
Sortie : permutation (réorganisation) !a1 , a2 , . . . , a!n " de la suite donnée en entrée,
d’exécuter des instruction élémentaires séquentiellement et en un temps
de façon que a!1 ! a!2 ! · · · ! a!n .
constant :
Les nombres à trier sont parfois appelés clés.
o Instructions
Dans arithmétiques
cet ouvrage, et logique
nous exprimerons (+, -, *, /, %,
généralement les …)
algorithmes sous la forme
de programmes écrits en un pseudo code qui, à certains égards, rappelle C, Pascal
o Lecture / écriture dans la mémoire (Affectation)
ou Java. Si vous connaissez déjà l’un de ces langages, vous n’aurez guère de mal à
lireInstructions
o de contrôle
nos algorithmes. Ce qui différencie le pseudo code du « vrai » code c’est que,
avec le pseudo code nous employons l’écriture qui nous semble être la plus claire
et laAppels
o de fonction
plus concise pour spécifier l’algorithme ; ne soyez donc pas surpris de voir ap-
paraître un mélange de français et de « vrai » code. Autre différence entre pseudo
• è Ces instructions ont un coût constant.
code et vrai code : le pseudo code ne se soucie pas, en principe, de problèmes d’ingé-
nierie logicielle tels qu’abstraction des données, modularité, traitement d’erreur, etc.
Cela permet au pseudo code de refléter plus clairement la substantifique moelle de
l’algorithme.
Nous commencerons par le tri par insertion, qui est un algorithme efficace quand il
E. Zemmouri, ENSAM - Meknès 5
s’agit de trier un petit nombre d’éléments. Le tri par insertion s’inspire de la manière
dont la plupart des gens tiennent des cartes à jouer. Au début, la main gauche du
joueur est vide et ses cartes sont posées sur la table. Il prend alors sur la table les
cartes, une par une, pour les placer dans sa main gauche. Pour savoir où placer une
carte dans son jeu, le joueur la compare avec chacune des cartes déjà présentes dans
sa main gauche, en examinant les cartesAdenlaa droite
l y s evers
du la gauche,
t r i pcomme
a r i nlesmontre
ertion
la figure 2.1. A tout moment, les cartes tenues par la main gauche sont triées ; ces
cartes étaient, à l’origine, les cartes situées au sommet de la pile sur la table.
♣♣ ♣
7
♣
♣♣
5♣ ♣
4 ♣♣ ♣♣ ♣
10
2 ♣
♣ ♣♣♣
♣
♣
♣
♣ ♣
7
♣ ♣♣ ♣
♣
♣
5♣4 2♣
♣♣♣
♣♣ ♣
10
Figure 2.1 Tri de cartes à jouer, via tri par insertion.
E. Zemmouri, ENSAM - Meknès 6
Notre pseudo-code pour le tri par insertion se présente sous la forme d’une procé-
dure appelée T RI -I NSERTION. Elle prend comme paramètre un tableau A[1 . . n] qui
22/02/20
E. Zemmouri, ENSAM - Meknès 7
Conception des algorithmes
E. Zemmouri, ENSAM - Meknès 8
22/02/20
Conception des algorithmes
• Différentes approches pour concevoir un algorithme
• Approche incrémentale :
o Le tri par insertion utilise une approche incrémentale.
o Après avoir trié le sous-tableau T[0] à T[i-1], on insère l’élément T[i]
à la bonne position pour produire le sous-tableau trié T[0] à T[i].
E. Zemmouri, ENSAM - Meknès 9
Méthode Divide and Conquer
• L’approche Divide and Conquer (diviser pour régner ):
o Divide : Diviser le problème en plusieurs sous-problèmes semblables au
problème initial mais de taille moindre.
o Conquer : Résoudre les sous-problèmes de manière récursive. Si la taille d’un
sous-problème est suffisamment réduite, on peut toutefois le résoudre
directement.
o Combine : Combiner toutes les solutions pour produire la solution du
problème de départ.
E. Zemmouri, ENSAM - Meknès 10
22/02/20
Exemple : tri par fusion
• L’algorithme du tri par fusion suit fidèlement le paradigme Divide and
Conquer :
o Divide : Diviser le tableau de n éléments à trier en deux sous-tableaux de n/2
éléments chacun.
o Conquer : Trier les deux sous-tableaux de manière récursive en utilisant le tri
par fusion.
o Combine : Fusionner les deux sous-tableaux triées.
o La récursivité s’arrête quand la séquence à trier a une longueur 1, auquel cas il
n’y a plus rien à faire puisqu’un tableau de taille 1 est déjà triée.
E. Zemmouri, ENSAM - Meknès 11
Tr i p a r f u s i o n
E. Zemmouri, ENSAM - Meknès 12
22/02/20
Notation asymptotique
E. Zemmouri, ENSAM - Meknès 13
Croissance des fonctions
• Analyser la complexité d’un algorithme :
o C’est étudie la façon dont augmente à la limite le temps d’exécution de cet
algorithme quand la taille de l’entrée augmente indéfiniment.
o è On étudie les performances asymptotiques des algorithmes.
o è Pour des entrées suffisamment grandes, les effets des constantes
multiplicatives et des termes d’ordre inférieur d’un temps d’exécution exact
sont négligeables par rapport aux effets de la taille de l’entrée.
E. Zemmouri, ENSAM - Meknès 14
22/02/20
Notation asymptotique
• C’est une notation classique pour la simplification de l’analyse
asymptotique des algorithmes.
• Notation définie en termes de fonctions dont le domaine de définition est
l’ensemble ℕ = {0, 1, 2, … }.
• L’objectif est de décrire la fonction 𝑇(𝑛) donnant le temps d’exécution du
pire cas ( cas le plus défavorable).
E. Zemmouri, ENSAM - Meknès 15
Notation 𝚯
• Pour une fonction 𝑔 𝑛 donnée, on note Θ(𝑔 𝑛 ) l’ensemble des
fonctions suivant :
𝜣 𝒈 𝒏 = 𝒇 𝒏 ∃ 𝒄𝟏 ≥ 𝟎, 𝒄𝟐 ≥ 𝟎 𝒆𝒕 𝒏𝟎 𝒕𝒆𝒍𝒍𝒆𝒔 𝒒𝒖𝒆
3.1 Notation asymptotique
𝟎 ≤ 𝒄𝟏 𝒈 𝒏 ≤ 𝒇 𝒏 ≤ 𝒄𝟐 𝒈 𝒏 𝒑𝒐𝒖𝒓 𝒕𝒐𝒖𝒕 𝒏 ≥ 𝒏𝟎 }
c2 g(n)
• On écrit : f (n)
o 𝑓 𝑛 ∈ Θ(𝑔 𝑛 ) c1 g(n)
o Ou par abus : 𝒇 𝒏 = 𝜣(𝒈 𝒏 )
• On dit que : n0
n
f (n) = Q(g(n))
o 𝑔(𝑛) est une borne asymptotiquement approchée de 𝑓 (𝑛) (a)
Figure 3.1 Exemples de notations Q
E. Zemmouri, ENSAM - Meknès nimale possible ; n’importe quelle
16 vale
une fonction entre des facteurs const
tives n0 , c1 et c2 telles que, à droite d
et c2 g(n) inclus. (b) La notation O do
constant près. On écrit f(n) = O(g(n)) s
de n0 , la valeur de f(n) soit toujours
borne inférieure pour une fonction à
22/02/20
Notation 𝚯
• Exemples :
$
o 𝑇 𝑛 = % 𝑛% − 3𝑛 + 5 = Θ(𝑛% )
o 𝑇 𝑛 = 𝑎𝑛% + 𝑏𝑛 + 𝑐 = Θ 𝑛% 𝑝𝑜𝑢𝑟 𝑎 > 0 è Complexité quadratique
o 𝑇 𝑛 =𝑐=Θ 1 𝑝𝑜𝑢𝑟 𝑐 > 0 è Complexité constante
o 𝑇 𝑛 = ∑)&'( 𝑎& 𝑛& = Θ 𝑛) 𝑝𝑜𝑢𝑟 𝑎) > 0 è Complexité polynomiale
o 𝑇 𝑛 = 6𝑛𝑙𝑜𝑔 𝑛 + 𝑏𝑛 + 𝑐 = Θ 𝑛𝑙𝑜𝑔(𝑛) è Complexité quasi-linéaire
• è On néglige les termes d’ordre inférieur et les constantes pour le calcul
d’une borne asymptotique approchée.
E. Zemmouri, ENSAM - Meknès 17
Notation 𝑶
• Pour une fonction 𝑔 𝑛 donnée, on note O(𝑔 𝑛 ) l’ensemble des
fonctions suivant :
𝑶 𝒈 𝒏 = 𝒇 𝒏 ∃ 𝒄 ≥ 𝟎 𝒆𝒕 𝒏𝟎 𝒕𝒆𝒍𝒍𝒆𝒔 𝒒𝒖𝒆
3.1 Notation asymptotique
𝟎 ≤ 𝒇 𝒏 ≤ 𝒄𝒈 𝒏 𝒑𝒐𝒖𝒓 𝒕𝒐𝒖𝒕 𝒏 ≥ 𝒏𝟎 }
c2 g(n) cg(n)
• On écrit :
f (n)
f (n)
o 𝑓 𝑛 ∈ 𝑂(𝑔 𝑛 ) c1 g(n)
o Ou par abus : 𝒇 𝒏 = 𝑶(𝒈 𝒏 )
• On dit que : n n
n0 n0
f (n) = Q(g(n)) f (n) = O(g(n))
o 𝑔(𝑛) est une borne supérieure asymptotique
(a) de 𝑓 (𝑛) (b)
Figure 3.1 Exemples de notations Q, O et . Dans chaque partie, la valeur
E. Zemmouri, ENSAM - Meknès 18
nimale possible ; n’importe quelle valeur supérieure ferait aussi l’affaire. (a
une fonction entre des facteurs constants. On écrit f(n) = Q(g(n)) s’il exist
tives n0 , c1 et c2 telles que, à droite de n0 , la valeur de f(n) soit toujours
et c2 g(n) inclus. (b) La notation O donne une borne supérieure pour une
constant près. On écrit f(n) = O(g(n)) s’il existe des constantes positives n0
de n0 , la valeur de f(n) soit toujours inférieure ou égale à cg(n). (c) La n
borne inférieure pour une fonction à un facteur constant près. On écrit f
22/02/20
Notation 𝑶
• La notation 𝑂 sert à majorer une fonction, à un facteur constant près.
• Quand on l’utilise pour borner le temps d’exécution du pire cas d’un
algorithme, on borne donc aussi le temps d’exécution de cet algorithme
pour des entrées quelconques.
• La notation 𝑂 est généralement plus simple à évaluer que la notation Θ
o On peut décrire le temps d’exécution en étudiant la structure globale de
l’algorithme.
E. Zemmouri, ENSAM - Meknès 19
Notation 𝛀
• Pour une fonction 𝑔 𝑛 donnée, on note Ω(𝑔 𝑛 ) l’ensemble des
fonctions suivant :
𝛀 𝒈 𝒏 = 𝒇 𝒏 ∃ 𝒄 ≥ 𝟎 𝒆𝒕 𝒏𝟎 𝒕𝒆𝒍𝒍𝒆𝒔 𝒒𝒖𝒆
3.1 Notation asymptotique 41
𝟎 ≤ 𝒄𝒈 𝒏 ≤ 𝒇(𝒏) 𝒑𝒐𝒖𝒓 𝒕𝒐𝒖𝒕 𝒏 ≥ 𝒏𝟎 }
c2 g(n) cg(n)
• On écrit : f (n)
f (n)
f (n)
o 𝑓 𝑛 ∈ Ω(𝑔 𝑛 ) c1 g(n) cg(n)
o Ou par abus : 𝒇 𝒏 = 𝛀(𝒈 𝒏 )
• On dit que : n n n
n0 n0 n0
f (n) = Q(g(n)) f (n) = O(g(n)) f (n) = V(g(n))
o 𝑔(𝑛) est une borne
(a) inférieure asymptotique
(b) de 𝑓 (𝑛) (c)
Figure 3.1 Exemples de notations Q, O et . Dans chaque partie, la valeur de n0 est la valeur mi-
E. Zemmouri, ENSAM - Meknès 20
nimale possible ; n’importe quelle valeur supérieure ferait aussi l’affaire. (a) La notation Q borne
une fonction entre des facteurs constants. On écrit f(n) = Q(g(n)) s’il existe des constantes posi-
tives n0 , c1 et c2 telles que, à droite de n0 , la valeur de f(n) soit toujours comprise entre c1 g(n)
et c2 g(n) inclus. (b) La notation O donne une borne supérieure pour une fonction à un facteur
constant près. On écrit f(n) = O(g(n)) s’il existe des constantes positives n0 et c telles que, à droite
de n0 , la valeur de f(n) soit toujours inférieure ou égale à cg(n). (c) La notation V donne une
borne inférieure pour une fonction à un facteur constant près. On écrit f(n) = V(g(n)) s’il existe
22/02/20
Propriétés
• 𝒇 𝒏 =𝜣 𝒈 𝒏 ⟹ 𝒇 𝒏 =𝑶 𝒈 𝒏
o C’est-à-dire 𝜣 𝒈 𝒏 ⊆𝑶 𝒈 𝒏
• 𝒇 𝒏 =𝜣 𝒈 𝒏 ⟹ 𝒇 𝒏 =𝜴 𝒈 𝒏
o C’est-à-dire 𝜣 𝒈 𝒏 ⊆𝛀 𝒈 𝒏
• 𝒇 𝒏 =𝜣 𝒈 𝒏 ⟺ 𝒇 𝒏 =𝜴 𝒈 𝒏 𝒆𝒕 𝒇 𝒏 = 𝑶 𝒈 𝒏
E. Zemmouri, ENSAM - Meknès 21
Fonctions de complexités classiques
Complexité Nom
𝑶(𝟏) Constante
𝑶 𝐥𝐨𝐠 𝒏 Logarithmique
𝑶𝒏 Linéaire
𝑶 𝐧𝐥𝐨𝐠 𝒏 Quasi-linéaire
𝑶 𝒏𝟐 Quadratique
𝑶 𝒏𝒌 pour k > 2 Polynomiale
𝑶 𝒄𝒏 pour c > 1 Exponentielle
𝑶 𝒏! Factorielle
E. Zemmouri, ENSAM - Meknès 22
22/02/20
Exercices exemples
• Evaluation d’un polynôme de degré n
o Algorithme naïf et schéma de Horner
• Calcul de puissance
o Direct et avec Divide and Conquer
• Recherche dans un tableau
o Recherche séquentielle et dichotomique
E. Zemmouri, ENSAM - Meknès 23
The Master Method
(Méthode générale)
E. Zemmouri, ENSAM - Meknès 24
22/02/20
The Master Method
• La méthode générale donne une « recette » pour analyser le temps
d’exécution d’un problème récursif
o En particulier Divide and Conquer
• Hypothèse :
o Les sous problèmes résultant de la phase « Divide » sont de même taille
E. Zemmouri, ENSAM - Meknès 25
Récurrence
• Initialisation :
o 𝑇 𝑛 ≤ 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑒 Pour n suffisamment petit.
• Pour tout n grand :
*
o 𝑇 𝑛 ≤ 𝑎𝑇 + 𝑂(𝑛) )
+
o 𝑎 = le nombre d’appels récursifs 𝑎 ≥ 1
o 𝑏 = facteur de division du problème 𝑏 > 1
o 𝑂(𝑛) ) = temps d’exécution de la phase Combine
o a, b et d sont des constantes indépendantes de n
E. Zemmouri, ENSAM - Meknès 26
22/02/20
The Master Method
𝑂 𝑛W log 𝑛 𝑠𝑖 𝑎 = 𝑏W
𝑇 𝑛 = 𝑂 𝑛W 𝑠𝑖 𝑎 < 𝑏W
𝑂 𝑛XYZ! [ 𝑠𝑖 𝑎 > 𝑏W
E. Zemmouri, ENSAM - Meknès 27
Exemples
• Tri par fusion :
*
o 𝑇 𝑛 = 2𝑇 %
+𝑂 𝑛
o è 𝑇 𝑛 = 𝑂 𝑛𝑙𝑜𝑔 𝑛
• Recherche dichotomique :
*
o 𝑇 𝑛 =𝑇 %
+𝑂 1
o è 𝑇 𝑛 = 𝑂 𝑙𝑜𝑔 𝑛
E. Zemmouri, ENSAM - Meknès 28
22/02/20
Programmation avancée
Complexité algorithmique
EL Moukhtar ZEMMOURI
ENSAM – Meknès
Version – 1.0