Pf00cours Texte XXX

Preuve et Notations asymptotiques [pf]
Support de cours
Karine Zampieri, Stéphane Rivière, Béatrice Amerein-Soltner
Unisciel algoprog Version 22 mai 2018
Table des matières

1 Terminaison d’un algorithme 3
1.1 Méthode de Floyd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Exemple : Méthode de Floyd . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Exemple : Méthode de Knuth . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Validité d’un algorithme 8

2.1 Récurrence à partir d’invariant . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Exemple : Calcul de la puissance . . . . . . . . . . . . . . . . . . . . . . 8
3 Évaluation du coût d’un calcul 10

3.1 Principe de l’évaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Exemple : Évaluation du coût de la fonction gerase . . . . . . . . . . . . 10
4 Notations asymptotiques 12
4.1 Définitions des notations asymptotiques . . . . . . . . . . . . . . . . . . . 12
4.2 Propriétés fondamentales . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.3 Principales classes de complexité . . . . . . . . . . . . . . . . . . . . . . 15
5 Exemple : Calcul de la puissance 17

5.1 Premier algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.2 Deuxième algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6 Exemple : Analyse du tri simple 19

6.1 Algorithme générique du tri simple . . . . . . . . . . . . . . . . . . . . . 19
6.2 Analyse du tri bulle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6.3 Analyse du tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.4 Analyse du tri par sélection . . . . . . . . . . . . . . . . . . . . . . . . . 21
7 Conclusion 22
1
Unisciel algoprog – pf00cours-texte, May 22, 2018 2
Preuve et Notations asymptotiques (Cours)

Mots-Clés Preuve et Notations asymptotiques
Requis Axiomatique impérative sauf Fichiers
Difficulté • • ◦
Introduction
Ce module présente des méthodes qui permettent de « prouver un algorithme » c.-à-d. de
vérifier qu’un algorithme partiellement correct se termine et de montrer qu’il est valide.
Il donne ensuite deux approches de l’évaluation du coût en temps d’exécution d’un al-
gorithme. La première montre comment totaliser les coûts élémentaires dans le cas où
le nombre de calculs est assez simple à évaluer. La deuxième donne les définitions et
les propriétés des notations asymptotiques utilisées en informatique puis les applique au
travers de deux exemples.
1 Terminaison d’un algorithme
1.1 Méthode de Floyd
Les instructions pouvant faire qu’un algorithme ne se termine pas sont les itérations et les
appels de sous-algorithmes. Malheureusement il n’existe pas d’algorithme général pour
faire la preuve de terminaison mais seulement des méthodes pour des cas particuliers.
Nous nous intéressons ici à l’itération en considérant les méthodes de Floyd et de
Knuth.
Terminaison par la méthode de Floyd

En 1967, la méthode suggérée par Floyd repose sur le fait que l’ensemble N des entiers
naturels muni de la relation > est telle qu’il n’existe pas de suite infinie descendante telle
que :
n1 > n2 > . . . > ni > . . .
A chaque itération :
PRECOND P
TantQue B(x) Faire S(x) Fait
POSTCOND P et non B(x)
elle consiste à associer une fonction f qui est telle que :

• le domaine de définition est l’ensemble des valeurs de x = (x1 , x2 , . . . , xn ),
• l’ensemble des valeurs est l’ensemble Z des entiers relatifs,
• f (x) > f (S(x)) où S(x) est la valeur de la variable informatique x modifiée par
l’exécution du corps S de l’itération,
• f (x) ≤ 0 quand ¬B(x) est réalisée.
Terminaison par la méthode des compteurs de Knuth

La méthode de Floyd ne fournit pas de majorant qui permet d’apprécier raisonnable-
ment la performance de l’algorithme. Pour cela, en 1968, Knuth a suggéré d’introduire
de nouvelles variables entières, appelées compteurs, qui sont augmentées de 1 à chaque
passage dans le corps de l’itération. Si l’on peut montrer que la condition non B(x) ex-
prime que la croissance des compteurs est bornée alors, non seulement on aura prouvé
que l’algorithme se termine, mais on aura aussi une évaluation du nombre de fois que
l’algorithme a exécuté le corps de l’itération.
1.2 Exemple : Méthode de Floyd
Considérons l’algorithme de De Gerase qui calcule le PGCD (plus grand commun

multiple) de deux entiers positifs a et b par soustraction du plus petit dans le plus grand
des deux entiers jusqu’à ce qu’ils soient égaux.
Fonction gerase
(PGCD de deux entiers a et b)
Fonction gerase ( a : Entier ; b : Entier ) : Entier
Variable x , y : Entier
Début
| x <- a
| y <- b
| TantQue ( x <> y ) Faire
| | Si ( x > y ) Alors
| | | x <- x - y
| | Sinon
| | | y <- y - x
| | FinSi
| FinTantQue
| Retourner ( x )
Fin
Terminaison
Pour prouver la terminaison de cette itération par la méthode de Floyd, associons la
fonction f telle que :
f (x, y) = |x − y| x y
Considérons les trois cas possibles.
1. D’abord le cas où x > y > 0. Alors :
f (S(x, y)) = f (x − y, y)
= |(x − y) − y| (x − y) y
= |x − 2y| (x − y) y
Par conséquent :
f (S(x, y)) < f (x, y)
⇔ |x − 2y| (x − y) y < |x − y| x y
⇔ |x − 2y| < x
car x − y > 0 et y > 0. Comme x > 0, il faut que :
(x − 2y)2 < x2
⇔ 4y 2 − 4xy < 0
⇔ y(y − x) < 0
⇔ y−x < 0 car y > 0
ce qui est l’hypothèse de départ. Nous avons donc bien :
f (S(x, y)) < f (x, y)
2. Le cas où y > x > 0 s’obtient en permutant x et y.

3. Enfin lorsque f (x, y) = 0, nécessairement x = y parce que x et y sont positifs.
C’est la condition d’arrêt de l’itération.
Remarque
La valeur initiale f (a, b) peut servir de majorant pour le nombre d’itérations mais il peut
être considérablement plus grand que ce nombre. Par exemple, il y a deux itérations pour
gerase(24,16) alors que f (24, 16) = 8 × 24 × 16 = 3072.
1.3 Exemple : Méthode de Knuth
Considérons à nouveau l’algorithme de De Gerase pour le calcul du PGCD de deux

entiers. Modifions la fonction en introduisant trois compteurs :
• i est incrémenté toutes les fois que x > y
• j toutes les fois que y < x
• n toutes les fois que x <> y (c.-à-d. chaque fois que la fonction exécute le corps de
l’itération).
Les variables sont initialisées à zéro et après l’itération, nous avons l’assertion POSTCOND(n=i+j).
Fonction geraseKnuth
Fonction geraseKnuth ( a : Entier ; b : Entier ) : Entier
Variable i , j , n : Entier
Début
| i <- 0
| j <- 0
| n <- 0
| x <- a
| y <- b
| | | x <- x - y
| | | i <- i + 1
| | Sinon
| | | y <- y - x
| | | j <- j + 1
| | FinSi
| | n <- n + 1
| FinTantQue
| Retourner ( x )
Fin
Terminaison
Les compteurs et leurs incrémentations sont fictives et ne servent qu’à la preuve de
terminaison. Utilisons-les dans ce but.
1. Quand x > y le passage par le corps S de l’itération consiste à faire :
x <- x - y
i <- i + 1
Comme x est initialisé à a et qu’il reste positif, ce passage se fait au maximum a-1
fois. Donc 0 ≤ i ≤ a.
2. De même, on passe au maximum b-1 fois par le cas y < x, donc 0 ≤ j ≤ b.
On en déduit que 0 ≤ n ≤ a + b − 2.
Remarque
Ceci nous donne une preuve de convergence et une estimation grossière du nombre d’ité-
rations. Par exemple, geraseKnuth(24,16) s’exécute en deux itérations alors que cela donne
0 ≤ n ≤ 38.
2 Validité d’un algorithme

Un algorithme (O, V, S) est formé d’un ensemble fini O d’opérations liées par une struc-
ture de contrôle S et dont les opérandes portent sur un ensemble fini V de variables.
Un algorithme résout le problème P si pour tout énoncé I de P (stocké dans le sous-
ensemble des variables d’entrée de V), la suite des opérations exécutées est finie (condition
de terminaison) et lors de la terminaison le sous-ensemble des variables de sortie de V
contient le résultat associé à l’énoncé I (condition de validité). Prouver un algorithme,
c’est démontrer mathématiquement que la propriété précédente est satisfaite.
2.1 Récurrence à partir d’invariant
Soit alors un problème dont on recherche une solution à l’aide d’un algorithme itératif
qu’il faut expliciter à l’aide d’une récurrence à déterminer. On procède de la manière
suivante.
1. Écrire (voire inventer) l’hypothèse de récurrence, les suites qui l’expriment et l’in-
variant qui définit les propriétés de cette récurrence.
2. Établir le critère d’arrêt sous forme d’une propriété supplémentaire que doit pos-
séder un terme de l’une des suites. Ce critère d’arrêt permet de calculer le résultat
attendu.
3. Construire le système de définitions récurrentes (S.D.R.) associé aux suites. Ce
système se détermine par le souci de progresser vers la solution, c.-à-d. vers le
critère d’arrêt tout en réservant la propriété invariante tant que n’est pas atteint
l’état final correspondant au critère d’arrêt.
4. Déterminer les conditions initiales.
5. Prouver la convergence de l’algorithme.
2.2 Exemple : Calcul de la puissance
Objectif
Écrire une fonction efficace pour calculer xn avec x ∈ R et n ∈ N.
Hypothèse de récurrence et invariant

L’idée de la récurrence repose sur l’utilisation de la décomposition binaire de n et l’écri-
ture résultante de xn . Les relations de récurrence s’écrivent :

(xn div 2 )2 si n pair
xn =
xn−1 x sinon
avec x0 = 1. On définit alors un système de trois suites (xi ), (yi ), (zi ) possédant la
propriété invariante suivante :
xn = zi (xi )yi
Critère d’arrêt
Le critère d’arrêt est : 
i∗= PPETIT (i ≥ 0 : yi = 0)
resultat = z ∗ = z ∗
i
S.D.R. et pas de la récurrence

Le système de définitions récurrentes est le suivant :

xi+1

 = x2i

zi+1 = si impair(yi ) alors zi xi sinon zi finsi


yi+1 = yi div 2
Ces définitions sont construites pour préserver la propriété invariante. En effet, supposons
xn = zi (xi )yi et calculons zi+1 (xi+1 )yi+1 . Il vient alors :
• Si yi est pair, on a 2(yi div 2) = yi et
zi+1 (xi+1 )yi+1 = zi (x2i )yi div 2

= zi (xi )yi
= xn
• Si yi est impair, on a 2(yi div 2) + 1 = yi et
zi+1 (xi+1 )yi+1 = zi (x2i )yi div 2

= zi (xi )yi
= xn
Conditions initiales
x0 = x, y0 = n, z0 = 1
Convergence
Pour tout entier e > 0, on a e div 2 < e. On en déduit que yi+1 < yi et qu’on finit par
atteindre yi∗ = 0.
3 Évaluation du coût d’un calcul
3.1 Principe de l’évaluation
Pour évaluer le temps d’exécution d’un calcul, il faut évaluer et cumuler le temps que
requiert chaque instruction réalisant le calcul. Les facteurs qui influencent le temps d’exé-
cution sont :
• Les données du problème (l’instance particulière : taille et valeurs)
• L’algorithme utilisé pour résoudre le problème
Mais aussi :
• Le matériel (vitesse du processeur, taille et vitesse d’accès à la mémoire, temps de
transfert disque, etc.)
• Le logiciel (langage de programmation, compilateur/interpréteur, etc.)
• La charge de la machine (nombre de processus qui s’exécutent, etc.)
• Le système d’exploitation (gestion de différents processus, etc.)
• La charge du réseau (accès aux données, écriture des résultats, etc.)
• etc.
Il faudrait en toute rigueur se donner un modèle d’ordinateur et faire les calculs pour
l’architecture correspondante. Nous nous contentons d’un modèle très simplifié en ne
gardant que les temps élémentaires les plus importants, par exemple :
TAM : temps de transfert entre mémoire et unité centrale

TADD : temps d’une addition ou d’une soustraction
TM U L : temps d’une multiplication
TDIV : temps d’une division
TCM P : temps d’une comparaison d’un registre et de la valeur 0
TES : temps d’une entrée sortie
Pour plus de détails, le lecteur se reportera à un ouvrage d’architectures des ordinateurs,

par exemple [Andrew Tanenbaum, Architecture de l’ordinateur, Pearson Education, 5e
édition, 2005, ISBN-2-7440-7122-6].
3.2 Exemple : Évaluation du coût de la fonction gerase
Évaluons le temps de calcul du PGCD par la méthode de De Gérase de deux entiers

positifs a| et \lstinlineb| en supposant les entiers en mémoire et x| et \lstinliney| des
registres.
Fonction gerase
Fonction gerase ( a : Entier ; b : Entier ) : Entier

Début
| x <- a
| y <- b
| | | x <- x - y
| | Sinon
| | | y <- y - x
| | FinSi
| FinTantQue
| Retourner ( x )
Fin
Évaluation du coût
Si le nombre d’itérations est n, le temps de calcul Tgerase est voisin de :
Tgerase = 3TAM + n(3TADD + 2TCM P )
Explication
L’initialisation de x et de y induit deux transferts donc 2TAM . Ensuite la condition x <> y
de la structure TantQue entraı̂ne l’opération x - y suivie d’une comparaison à zéro donc
TADD + TCM P . La condition Si implique une nouvelle comparaison TADD + TCM P et la
clause Alors ou Sinon opère une soustraction donc TAM . Enfin l’opération Retourner induit
un transfert TAM . Finalement :
Tgerase = 2TAM + n(TADD + TCM P + TADD + TCM P + TADD ) + TAM

= 3TAM + n(3TADD + 2TCM P )
4 Notations asymptotiques
Il est en général impossible de calculer de façon précise le coût d’un algorithme. C’est tout
particulièrement la situation des problèmes non numériques où ces coûts sont fonction
de la répartition des variables.
C’est pour cela que, quelle que soit la machine utilisée, on considère que toutes les
opérations élémentaires sont effectuées en temps constant (égal à 1) et que l’on s’intéresse
à la variation du coût en fonction du nombre des données, plus exactement l’asymptote
vers laquelle tend ce coût lorsque la taille du problème augmente (c.-à-d. tend vers
l’infini).
On utilise alors les notations asymptotiques de Bachmann (dites également notations
de Landau) pour estimer l’utilisation des ressources d’un algorithme.
4.1 Définitions des notations asymptotiques
Les notations de Landau, lorsque g est une fonction de N dans N et quand n → +∞,
sont les suivantes :
Borne supérieure asymptotique

Est définie par (lire « Grand Oh ») :
O(g) = {f : N → N | ∃c ∈ R+ , ∃n0 ∈ N tels que ∀n ≥ n0 : 0 ≤ f (n) ≤ c g(n)}
Si une fonction f ∈ O(g), on dit que g est une borne supérieure asymptotique pour f .
On note abusivement : f = O(g).
Borne inférieure asymptotique

Est définie par (lire « Grand Omega ») :
Ω(g) = {f : N → N | ∃c ∈ R+ , ∃n0 ∈ N tels que ∀n ≥ n0 : 0 ≤ c g(n) ≤ f (n)}
Si une fonction f ∈ Ω(g), on dit que g est une borne inférieure asymptotique pour f .
On note abusivement : f = Ω(g).
Borne asymptotique
Est définie par (lire « Grand Theta ») :
Θ(g) = O(g) ∩ Ω(g)
Si une fonction f ∈ Θ(g), on dit que g est une borne asymptotique pour f .
On note abusivement : f = Θ(g).
Autre formulation : f ∈ Θ(g) si et seulement si f ∈ O(g) et f ∈ Ω(g).
Remarque
L’écriture explicite de la borne asymptotique est :
Θ(g) = {f : N → N | ∃c1 ∈ R+ , ∃c2 ∈ R+ , ∃n0 ∈ N tels que

∀n ≥ n0 : 0 ≤ c1 g(n) ≤ f (n) ≤ c2 g(n)}
Exemples
• n ∈ O(n), 2n ∈ O(3n), n + 2 ∈ O(n) (prenez n0 = 2 et c = 2)
√
• n ∈ O(n)
• log(n) ∈ O(n) (puisque log n ≤ n, ∀n ≥ 1)
• n ∈ O(n2 )
√
• n + n ∈ Ω(n + log(n))
√
• n + log(n) ∈ Θ(n + n)
Remarque
L’utilisation de la notation O permet de majorer le comportement d’une fonction, la
notation Ω de minorer le comportement d’une fonction et la notation Θ évite d’avoir une
majoration trop grossière. La notation Θ signifie qu’une fonction croı̂t au moins aussi
vite qu’une autre.
Analogie
Ces notations permettent donc de comparer deux fonctions. On pourra faire l’analogie
suivante avec la comparaison sur des nombres réels :
f (n) ∈ O(g(n)) ≈ a 6 b
f (n) ∈ Ω(g(n)) ≈ a > b
f (n) ∈ Θ(g(n)) ≈ a = b
4.2 Propriétés fondamentales
Les notations asymptotiques ont des propriétés qui découlent de leur définition.
Règle 1
Soient f et g des fonctions de N → N.
O(c f ) = c O(f ) (c est une constante)

O(f + g) = O(f ) + O(g) = max (O(f ), O(g))
O(f g) = O(f ) O(g)
f ∈ Ω(g) ⇔ g ∈ O(f )
f ∈ Θ(g) ⇔ f ∈ O(g) et g = O(f )
Règle 2
p
aj nj alors f (n) ∈ Θ(np )
X
Si f (n) =
j=0
Règle 3
logk (n) ∈ O(n) pour toute constante k
Remarques
• La règle 3 indique que les logarithmes croissent très lentement.
• Comme les constantes disparaissent dans l’analyse asymptotique, il suffit de comp-
ter les opérations primitives plutôt que les opérations élémentaires.
• Comme on ne manipule que des fonctions de N dans N et que l’on s’intéresse
uniquement à leur comportement à l’infini, on pourra sommer les O et les Θ sans
risque.
4.3 Principales classes de complexité
Puisque nous disposons d’un outil de comparaison, nous pouvons (d’après les règles
énoncées ci-avant) classer les algorithmes par complexité (c.-à.-d. quand on considère
N → ∞) croissante :
• Complexité constante si le coût est un Θ(1)
• Complexité logarithmique si le coût est un Θ(lg n) (ou par extension Θ(lg n)k )
• Complexité linéaire si le coût est un Θ(n)
• Complexité linéarithmique ou quasi-linéaire si le coût est un O(n lg n), mais
n’est pas un O(n)
• Complexité quadratique si le coût est un O(n2 )
• Complexité polynomiale le coût est un O(nk ) pour un certain k > 2
• Complexité exponentielle si le coût est un O(ρn ) pour un certain ρ > 1
• Complexité hyperexponentielle si pour tout ρ > 1, lim Tρ(n)
n = +∞ (par exemple
T (n) = n!)
Quelques remarques
Il convient de tenir présentes à l’esprit les remarques de bon sens suivantes :
1. En pratique, un algorithme de complexité quasi-linéaire se comporte comme s’il
avait une complexité linéaire. En effet, la taille des données qui lui sont soumises est
bornée ; il est raisonnable de considérer qu’elle ne peut pas dépasser 1015 , quantité
dont le logarithme est inférieur à 35.
2. L’emploi des notations O et Θ pour l’évaluation du coût d’un algorithme simplifie
notablement les calculs, mais peut cacher une partie de la réalité, à cause des
facteurs constants ignorés. Supposons que, pour résoudre un certain problème,
nous disposions de deux algorithmes de coût respectifs c(n) et d(n) ; si l’on nous
dit que c(n) = o(d(n)), nous sommes tentés de choisir le premier algorithme. Si nous
apprenons que c(n) = 100n alors que d(n) = n ln n, nous opterons bien évidemment
pour le deuxième algorithme.
3. On entend parfois l’expression « le coût de cet algorithme est au moins un O(n) » ;
il est clair que cette affirmation n’apporte aucune information sur le coût de l’al-
gorithme considéré.
Illustration du comportement
Le tableau ci-dessous illustre le comportement des classes de complexité envisagées plus
haut, sur quelques tailles de données.
n 100 1000 106 109

lg n <5 <7 <14 <21
n lg n <500 <7000 < 2107 < 31010
n2 104 106 1012 1018
n3 106 109 1018 1027
5 8
2n 1030 10300 > 1010 > 1010
Il est clair que les coûts qui apparaissent sur la dernière ligne de ce tableau sont (et
resterons) au-delà de nos moyens. (Note : on estime que l’âge de l’Univers est inférieur
à 1018 secondes.)
Remarque
La première figure est un zoom sur les fonctions constante, logarithmique, linéaire, li-
néarithmique et quadratique.
La deuxième figure illustre les fonctions g en algorithmique. Constatez la très forte crois-
sance à partir de la quadratique.
5 Exemple : Calcul de la puissance

Nous allons présenter deux manières permettant de calculer la puissance n-ème d’un réel
x et examiner leur complexité.
5.1 Premier algorithme
Une première manière de calculer la puissance est basée sur la récurrence
xn = xn−1 x pour n ≥ 1
avec x0 = 1. L’algorithme s’en déduit immédiatement.
Fonction puissanceNaif (Algorithme naı̈f)

Fonction puissanceNaif ( x : Réel ; n : Entier ) : Réel
Variable rs : Réel
Variable j : Entier
Début
| rs <- 1.0
| Pour j <- 1 à n Faire
| | rs <- rs * x
| FinPour
| Retourner ( rs )
Fin
Complexité
L’opération élémentaire significative ici est la multiplication. De façon évidente, T (n) =
n. On en déduit que l’algorithme est en Θ(n).
5.2 Deuxième algorithme
Une autre manière de calculer la puissance est basée sur la parité de n. Les relations de
récurrence s’écrivent 
(xn div 2 )2 si n pair
xn =  n−1
x x sinon
avec x0 = 1. L’algorithme s’écrit comme suit.
Fonction puissance (Algorithme basé sur la parité)

Fonction puissance ( x : Réel ; n : Entier ) : Réel
Variable rs , xn : Réel
Variable yn : Entier
Début
| rs <- 1.0
| xn <- x
| yn <- n
| TantQue ( yn <> 0 ) Faire

| | Si ( Modulo ( yn , 2 ) ) = 1 Alors
| | | rs <- rs * xn
| | FinSi
| | yn <- DivEnt ( yn , 2 )
| | xn <- xn * xn
| FinTantQue
| Retourner ( rs )
Fin
Complexité
Suivant la valeur de n, le nombre d’opérations élémentaires diffère :
• Pour n = 2k , il y a exactement k multiplications.
• Pour n = 2k − 1, il y en a 2(k − 1).
• Pour n ∈ [2k , 2k+1 [, on montre qu’il est de l’ordre de lg(n) multiplications.
On en déduit que la complexité est en O(lg(n)). L’algorithme basé sur cette deuxième
stratégie est donc meilleur que le premier proposé.
6 Exemple : Analyse du tri simple

Soit un tableau t d’éléments sur lequel il existe une relation d’ordre <. Le problème du
tri de t[1..n] consiste à ranger les éléments du tableau de telle façon que :
∀i, 1 ≤ i < n : t[i] ≤ t[i + 1]
Dans le tri, les opérations fondamentales sont la comparaison et l’échange de deux élé-
ments. De très nombreux algorithmes ont été proposés. Nous allons analyser le tri bulle,
le tri par insertion et le tri par sélection qui sont des méthodes de tri simples et faciles
à programmer. Nous verrons que le coût de ces méthodes est en O(n2 ).
6.1 Algorithme générique du tri simple
Le schéma général de ces algorithmes est le suivant :

1. On suppose que le tableau t est trié jusqu’au rang i-1.
2. On insère la valeur t[i] dans le sous-tableau t[1..i-1] de telle façon qu’après in-
sertion, le sous-tableau t[1..i] soit trié.
Schéma général d’un tri simple de t(1..n)

Action triSimple ( DR t : TypeElement [ TMAX ] ; n : Entier )
Variable ix : Entier
Début
| Pour ix <- 1 à n Faire
| | insererTri ( t , ix , n )
| FinPour
Fin
Complexité
Soit TIN S(i) le temps en terme d’opérations fondamentales pour exécuter insererTri(t,ix,n).
Le temps d’exécution du tri simple de n éléments est :
n
X
TT SIM P LE (n) = TIN S(i)
i=1
Remarque
Les procédures insererXXX utilisent la procédure permuter(t,j,k) qui a pour action de
permuter les éléments en position j et k du tableau t. Le coût de cette procédure est 3.
6.2 Analyse du tri bulle
La procédure insererBulle(t,k,n) consiste à faire « remonter » le plus petit élément du

sous-tableau t[k..n] en position k par une suite d’échanges de deux éléments consécutifs
du tableau. La procédure s’écrit :
Procédure d’insertion du tri à bulle

Action insererBulle ( DR t : TypeElement [ TMAX ] ; k : Entier ; n : Entier )
Début
| Pour ix <- n - 1 à k Pas - 1 Faire
| | Si ( t [ ix - 1 ] < t [ ix ] ) Alors
| | | permuterElement ( t , ix + 1 , ix )
| | FinSi
| FinPour
Fin
Complexité
Dans le pire des cas, l’élément t[n] se retrouve en t[k] en fin de procédure. C’est le cas
où t est initialement trié selon les valeurs décroissantes. Il y a une comparaison avec
résultat Vrai et donc un appel à la procédure permuterElement. D’où :
TMAX IBU L(k) = (n − 1 − k + 1)(1 + 3)

= 4(n − k)
Il en résulte :
n
X n
X
TMAX T BU LLE (n) = 4(n − i) = 4i
i=1 i=1
= 2n(n + 1)
= 2n2 + 2n
∈ O(n2 )
6.3 Analyse du tri par insertion
La procédure insererInsertion(t,k,n) insère l’élément t[k] dans le sous-tableau trié t[1..k-1]

par une suite d’échange de sorte que le sous-tableau t[1..k] soit trié. La procédure s’écrit :
Procédure d’insertion du tri par insertion

Action insererInsertion ( DR t : TypeElement [ TMAX ] ; k : Entier ; n : Entier )
Début
| ix <- k
| TantQue ( ix > 1 ) Et ( t [ ix ] < t [ ix - 1 ] ) Faire
| | permuterElement ( t , ix + 1 , ix )
| FinTantQue
Fin
Complexité
Dans le pire des cas, l’élément en k remonte jusqu’à l’indice 1. Le coût de cette procédure
est alors :
TMAX IIN S(k) = (k − 1)(1 + 3)
= 4(k − 1)
Il en résulte :
n
X
TMAX T IN SERT ION (n) = 4(i − 1)
i=1
∈ O(n2 )
6.4 Analyse du tri par sélection
La procédure insererSelection(t,k,n) détermine l’indice d’un élément minimum dans le

sous-tableau t[k..n] puis permute cet élément avec celui en t[k]. La procédure s’écrit
comme suit.
Procédure d’insertion du tri par sélection

Action insererSelection ( DR t : TypeElement [ TMAX ] ; k : Entier ; n : Entier )
Variable imin : Entier
Début
| imin <- k
| Pour ix <- k + 1 à n Faire
| | Si ( t [ ix ] < t [ imin ] ) Alors
| | | imin <- ix
| | FinSi
| FinPour
| Si ( imin <> k ) Alors
| | permuterElement ( t , imin , k )
| FinSi
Fin
Complexité
Le coût de cette procédure est :
TISEL(k) = (n − k + 1) + 3
= (n − k + 4)
Il en résulte :
n
X
TT SELECT ION (n) = (n − i + 4)
i=1
Xn
' (i + 4)
i=1
∈ Θ(n2 )
7 Conclusion
Terminaison
Un algorithme (O, V, S) est formé d’un ensemble fini O d’opérations liées par une struc-
ture de contrôle S et dont les opérandes portent sur un ensemble fini V de variables.
Un algorithme résout le problème P si pour tout énoncé I de P (stocké dans le sous-
ensemble des variables d’entrée de V), la suite des opérations exécutées est finie (condition
de terminaison) et lors de la terminaison le sous-ensemble des variables de sortie de V
contient le résultat associé à l’énoncé I (condition de validité). Prouver un algorithme,
c’est démontrer mathématiquement que la propriété précédente est satisfaite.
Complexité d’un algorithme

Une mesure de complexité d’un algorithme est une estimation de son temps de calcul, de
sa mémoire utilisée ou de toute autre unité significative. On s’intéresse le plus souvent
à la recherche d’une estimation par excès à une constante positive multiplicative près
du cas le plus défavorable sur le sous-ensemble des énoncés de taille fixée n (complexité
dite « pire-cas »). On obtient ainsi le taux asymptotique de croissance de la mesure
indépendamment de la machine sur laquelle l’algorithme est exécuté et l’on peut alors
comparer les complexités pire-cas de plusieurs algorithmes résolvant un même problème.
Notations asymptotiques
• Pire cas : f = O(g) ⇔ ∃n0 , ∃c > 0, ∀n ≥ n0 , f (n) ≤ c g(n)
• Meilleur cas : f = Ω(g) ⇔ g = O(f )
• Cas moyen : f = Θ(g) ⇔ f = O(g) et g = O(f )

Pf00cours Texte XXX

Transféré par

Droits d'auteur :

Formats disponibles

Pf00cours Texte XXX

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Pf00cours Texte XXX

Transféré par

Droits d'auteur :

Formats disponibles

Preuve et Notations asymptotiques [pf]

Karine Zampieri, Stéphane Rivière, Béatrice Amerein-Soltner

Unisciel algoprog Version 22 mai 2018

Table des matières

2 Validité d’un algorithme 8

3 Évaluation du coût d’un calcul 10

5 Exemple : Calcul de la puissance 17

6 Exemple : Analyse du tri simple 19

Preuve et Notations asymptotiques (Cours)

1 Terminaison d’un algorithme

1.1 Méthode de Floyd

Terminaison par la méthode de Floyd

elle consiste à associer une fonction f qui est telle que :

Terminaison par la méthode des compteurs de Knuth

1.2 Exemple : Méthode de Floyd

Considérons l’algorithme de De Gerase qui calcule le PGCD (plus grand commun

2. Le cas où y > x > 0 s’obtient en permutant x et y.

1.3 Exemple : Méthode de Knuth

Considérons à nouveau l’algorithme de De Gerase pour le calcul du PGCD de deux

2 Validité d’un algorithme

2.1 Récurrence à partir d’invariant

2.2 Exemple : Calcul de la puissance

Hypothèse de récurrence et invariant

S.D.R. et pas de la récurrence

zi+1 (xi+1 )yi+1 = zi (x2i )yi div 2

• Si yi est impair, on a 2(yi div 2) + 1 = yi et

zi+1 (xi+1 )yi+1 = zi (x2i )yi div 2

3 Évaluation du coût d’un calcul

3.1 Principe de l’évaluation

TAM : temps de transfert entre mémoire et unité centrale

Pour plus de détails, le lecteur se reportera à un ouvrage d’architectures des ordinateurs,

3.2 Exemple : Évaluation du coût de la fonction gerase

Évaluons le temps de calcul du PGCD par la méthode de De Gérase de deux entiers

Fonction gerase ( a : Entier ; b : Entier ) : Entier

Tgerase = 3TAM + n(3TADD + 2TCM P )

Tgerase = 2TAM + n(TADD + TCM P + TADD + TCM P + TADD ) + TAM

4.1 Définitions des notations asymptotiques

Borne supérieure asymptotique

O(g) = {f : N → N | ∃c ∈ R+ , ∃n0 ∈ N tels que ∀n ≥ n0 : 0 ≤ f (n) ≤ c g(n)}

Borne inférieure asymptotique

Ω(g) = {f : N → N | ∃c ∈ R+ , ∃n0 ∈ N tels que ∀n ≥ n0 : 0 ≤ c g(n) ≤ f (n)}

Θ(g) = O(g) ∩ Ω(g)

Θ(g) = {f : N → N | ∃c1 ∈ R+ , ∃c2 ∈ R+ , ∃n0 ∈ N tels que

4.2 Propriétés fondamentales

O(c f ) = c O(f ) (c est une constante)

logk (n) ∈ O(n) pour toute constante k

4.3 Principales classes de complexité

n 100 1000 106 109

5 Exemple : Calcul de la puissance

5.1 Premier algorithme

Une première manière de calculer la puissance est basée sur la récurrence

avec x0 = 1. L’algorithme s’en déduit immédiatement.

Fonction puissanceNaif (Algorithme naı̈f)

5.2 Deuxième algorithme

Fonction puissance (Algorithme basé sur la parité)

| TantQue ( yn <> 0 ) Faire

6 Exemple : Analyse du tri simple

6.1 Algorithme générique du tri simple

Le schéma général de ces algorithmes est le suivant :