Analyse des algorithmes

et
Complexité Algorithmique

1
 La question abordée:

Comment choisir parmi les différentes

approches (méthodes) pour
résoudre un problème?

2
• Définition: Un algorithme est un ensemble
d’actions permettant de transformer un
ensemble de données en un ensemble de
résultats, en un nombre fini d’étapes.

• Pour atteindre cet objectif, un algorithme

utilise deux ressources d’une machine:
le temps et l’espace mémoire.

3
 Analyse d’un algorithme
• Il existe souvent plusieurs algorithmes pour
résoudre un problème.
– ex. Tris, …
• On veut donc choisir l’algorithme le plus efficace:
– Au point de vue de la vitesse d’exécution
– De la quantité de mémoire de travail utilisée
• Un autre point peut entrer en ligne de compte : la
simplicité de l’algorithme.

4
• Définition 1: la complexité temporelle d’un
algorithme est le temps mis par ce dernier
pour transformer les données du problème
considéré en un ensemble de résultats.

5
• Définition 2: la complexité spatiale d’un
algorithme est l’espace utilisé par ce dernier
pour transformer les données du problème
considéré en un ensemble de résultats.

6
 Comparaison de solutions
Pour comparer des solutions entre-elles, deux
méthodes peuvent être utilisées:

• Étude empirique: (exécuter le programme)

• Analyse mathématique

Cette comparaison se fera, en ce qui nous concerne,

relativement à deux ressources critiques: temps,
espace mémoire,...

Nous allons nous concentrer beaucoup plus sur le

temps d’exécution 7
 Facteurs affectant le temps d’exécution:
1. machine,
2. langage,
3. programmeur,
4. compilateur,
5. algorithme et structure de données.

Le temps d’exécution dépend de la longueur de l’entrée.

Ce temps est une fonction T(n) où n est la longueur des
données d’entrée.

8
 Exemples (suite)
Exemple: x:=3; la longueur des données dans
ce cas est limitée à une seule variable.
Exemple :
S:= 0;
Pour i:=0 à n
Faire
Pour j:=0 à n
Faire
S:=S+1;
Fait;
Fait;
En revanche, dans ce cas, elle est fonction
du paramètre n

9
• La longueur des données d’entrée,
définissant le problème considéré, est
définie comme étant l’espace qu’elle
occupe en mémoire.

10
Pire cas, meilleur cas et cas moyen
Toutes les entrées d’une longueur donnée ne nécessitent
pas nécessairement le même temps d’exécution.
Exemple:

soit à rechercher un élément C dans un tableau de n

élément triés dans un ordre croissant.

Considérons les solutions suivantes:

1. Recherche séquentielle dans un tableau de taille n.
Commencer au début du tableau et considérer
chaque élément jusqu’à ce que l’élément cherché
soit trouvé.

11
2. Recherche dichotomique: tient compte du
fait que les éléments du tableau soient déjà
triés. Information ignorée par l’algorithme
de la recherche séquentielle.

• Ces deux algorithmes sont présentés comme

suit:

12
Fonction recherche1(Entrée tab: Tableau[n] entier; C: entier): Entier;
Debut
Var
i : Entier; b: Booléen;
i := 1; b:=Faux;
Tantque (i<=n Et non b)
Faire
Si tab[i] = C Alors b:=Vrai;
Sinon i:=i+1;
Fsi;
Fait;
Si (non b) Alors Recherche1:= -1;
Sinon Recherche1:= i;
Fsi;
Fin; /* fin de la fonction */

13
Fonction recherche2(Entrée tab: Tableau[n] entier; C: entier): Entier;

Début
Var
sup, inf, milieu: Entier;
trouve: Booléen;
inf := 1; sup :=n; trouve := faux;
Tantque (sup >=inf et non trouve)
Faire
milieu = [(inf + sup) / 2];
Si (C = tab[milieu]) Alors trouve :=Vrai;
Sinon
Si (C < tab[milieu])
Alors sup := milieu -1;
Sinon inf := milieu + 1;
Fsi;
Fsi;
Fait;
Si (non trouve) Alors Recherche2:=-1;
Sinon Recherche2:= milieu;
Fsi;
Fin; /* fin de la fonction */
14
 La méthode empirique

• Elle consiste à coder et exécuter deux (ou

plus) algorithmes sur une batterie de
données générées d’une manière aléatoire;
• À chaque exécution, le temps d’exécution
de chacun des algorithmes est mesuré.
• Ensuite, une étude statistique est entreprise
pour choisir le meilleur d’entre-eux à la
lumière des résultats obtenus.

15
 Problème!
Ces résultats dépendent

• de la machine utilisée;
• du jeu d’instructions utilisées
• de l’habileté du programmeur
• du jeu de données générées
• du compilateur choisi
• de l’environnement dans lequel est exécuté les deux
algorithmes (partagé ou non)
• .... etc.

16
 Méthode mathématique
• Pour pallier à ces problèmes, une notion de
complexité plus simple mais efficace a été
proposée par les informaticiens.
• Ainsi, pour mesurer cette complexité, la méthode
mathématique, consiste non pas à la mesurer en
unité de temps (par exemple les secondes), mais à
faire le décompte des actions (instructions) de
base exécutées par ces deux algorithmes.

17
• Cette manière de procéder est justifiée par
le fait que la complexité d’un algorithme est
en grande partie induite par l’exécution des
instructions qui le composent.
Cependant, pour avoir une idée plus
précise de la performance d’un
algorithme, il convient de signaler que la
méthode expérimentale et mathématique
sont en fait complémentaires.

18
 Comment choisir entre plusieurs
solutions?
1. décompte des instructions
• Reconsidérons la solution 1 (recherche
séquentielle) et faisons le décompte des
instructions. Limitons-nous aux instructions
suivantes:

• Affectation notée par e

• Test noté par t
• Addition notée par a

19
• Il est clair que ce décompte dépend non seulement de la
valeur C mais aussi de celles des éléments du tableau.

• Par conséquent, il y a lieu de distinguer trois mesures

de complexité:

• 1. dans le meilleur cas

• 2. dans le pire cas
• 3. dans le cas moyen

20
• Meilleur cas: notée par tmin(n) représentant la complexité de l’algorithme
dans le meilleur des cas en fonction du paramètre n (ici le nombre
d’éléments dans le tableau).

• Pire cas: notée par tmax(n) représentant la complexité de l’algorithme dans le

pire cas en fonction du paramètre n (ici le nombre d’éléments dans le
tableau).

• Cas Moyen: notée par tmoy(n) représentant la complexité de l’algorithme

dans le cas moyen en fonction du paramètre n (ici le nombre d’éléments
dans le tableau). C’est-à-dire la moyenne de toutes les complexités, t(i),
pouvant apparaître pour tout ensemble de données de taille n (t(i) représente
donc la complexité de l’algorithme dans le cas où C se trouve en position i
du tableau). Dans le cas où l’on apparaître la probabilité P i de réalisation de
la valeur t(i), alors par définition, on a:
tmoy(n) = p1 t(1) + p2 t(2) + p3 t(3) + ... +pn t(n)

21
• Il est clair que pour certains algorithmes, il
n’y a pas lieu de distinguer entre ces trois
mesures de complexité. Cela n’a pas
vraiment de sens.

22
Meilleur cas pour la recherche séquentielle:
Le cas favorable se présente quand la valeur
C se trouve au début du tableau

tmin(n) =

23
Pire cas: Le cas défavorable se présente
quand la valeur C ne se trouve pas du tout
dans le tableau. Dans ce cas, l’algorithme
aura à examiner, en vain, tous les éléments.

tmax(n) =

24
Cas moyen: Comme les complexités favorable et défavorable
sont respectivement (e + 3t) et = (n+1)e + na + (2n+3)t, la
complexité dans le cas moyen va se situer entre ces deux
valeurs. Son calcul se fait comme suit:
Pour plus de simplicité, on suppose que C existe dans le
tableau. On suppose aussi que sa probabilité de présence
dans l’une des positions de ce tableau est de 1/n.
Si C est dans la position i du tableau, la complexité t(i) de
l’algorithme est:

25
 Analyse d’un Algorithme
• Analyse détaillée d’un algorithme:
– Avantage :Très précise
– Désavantage : Long à calculer

• Solution: Analyser asymptotiquement le

comportement de l’algorithme lorsque le(s)
paramètre(s) de l’algorithme tendent vers
l’infini:
– Avantage: Facile à calculer
– Désavantage: Moins précis
26
 Complexité asymptotique
• Le décompte d’instructions peut s’avérer fastidieux à
effectuer si on tient compte d’autres instructions telles que:
– accès à un tableau,
– E/S, opérations logiques,
– appels de fonctions,.. etc.
• De plus, même en se limitant à une seule opération, dans
certains cas, ce décompte peut engendrer des expressions
que seule une approximation peut conduire à une solution.
• Par ailleurs, même si les opérations élémentaires ont des
temps d’exécution constants sur une machine donnée, ils
sont différents néanmoins d’une machine à une autre.

27
Par conséquent:
• Pour ne retenir que les caractéristiques essentielles
d’une complexité, et rendre ainsi son calcul simple
(mais indicatif!), il est légitime d’ignorer toute
constante pouvant apparaître lors du décompte du
nombre de fois qu’une instruction est exécutée.
• Le résultat obtenu à l’aide de ces simplifications
représente ce qu’on appelle la complexité
asymptotique de l’algorithme considéré.

28
La complexité asymptotique d’un algorithme décrit
le comportement de celui-ci quand la taille n des
données du problème traité devient de plus en plus
grande, plutôt qu’une mesure exacte du temps
d’exécution.

29
• Une notation mathématique, permettant de
représenter cette façon de procéder, est
décrite dans ce qui suit:

30
 Notation O
• Détermine une borne supérieure
• Définition formelle : f(n) = O(g(n)) s’il existe deux constantes positives n 0 et c tel
que f(n) <= cg(n) pour tout n>n0

f(n) = O(g(n))

cg(n)

f(n)
temps

n0 n 31
 Notation O
La notation grand-O indique une borne
supérieure sur le temps d’exécution.

Exemple: Si T(n) = 3n2 +2

alors T(n)  O(n2).

32
 Notation O (Calcul analytique)
• Étant donné deux fonctions f(n) et g(n),
f(n) = O(g(n)) ssi:
 b >= 0,  n, f(n) / g(n) <= b
limn f(n) / g(n) 
Exemple:
f(n) = 3n2+6n+4 et g(n) = n2+3
limn f(n) / g(n) = 3
 3n2+6n+4 est O(n2+3)
n dit « f(n) est d’ordre de g(n) »
33
 Notation-O (Analyse d’un algorithme)
• Cherche une fonction simple qui décrit le comportement de l’algorithme dans le pire
cas.
– Exemples : O(n), O(n2), O(lg n)
• L’analyse est simplifiée selon les règles suivantes:
– Les constantes sont éliminées
– Seul le monôme avec le degré le plus élevé est conservé
• Exemple: f(n) = 3n2+5n+4 est O(n2)
f(n) vs n2
4000

3500

3000

2500
f(n)
2000
f(n)
1500
n2
1000

500

0
0 10 20 30 40 50 60
n (taille des données) 34
 Grand-O: Exemples
Exemple 1: Initialiser un tableau d’entiers

Pour i:=1 à n Faire Tab[i]=0 Fait;

Il y a n itérations
Chaque itération nécessite un temps constant c,
où c est une constante (accès au tableau + une
affectation).
Le temps est donc T(n)  cn
Donc T(n)  O(n)

35
 Exemples
Exemple 2: T(n) = c1n2 + c2n .
c1n2 + c2n  c1n2 + c2n2  (c1 + c2)n2
pour tout n 1.
T(n)  cn2 où c = c1 + c2 et n0 = 1.
Donc, T(n) = O(n2).

Exemple 3: T(n) = c. On écrit T(n) = O(1).

36
 Notation 
• Détermine une borne inférieure
• Définition formelle : f(n) = (g(n)) s’il existe deux constantes
positives n0 et c tel que cg(n) <= f(n) pour tout n>n0

f(n) = W (g(n))

f(n)

cg(n)
temps

n0 n
37
 Notation Calcul analytique
• Étant donné deux fonctions f(n) et g(n),
f(n) = (g(n)) ssi:
  b > 0,  n, f(n) / g(n) >= b
– limn f(n) / g(n) 
– Exemple:
f(n) = 3n2+6n+4 et g(n) = n+3
limn f(n) / g(n) = 
3n2+6n+4 est (n+3)
3n2+6n+4 est (n)

On dit « f(g) est en oméga g(n) »

38
 Grand-Omega

Signification: Pour de grandes entrées,

l’exécution de l’algorithme nécessite au
moins cg(n) étapes.

 Borne inférieure.

39
 Grand-Omega: Exemple
T(n) = c1n2 + c2n.

c1n2 + c2n  c1n2 pour tout n > 1.

T(n)  cn2 pour c = c1 et n0 = 1.

Ainsi, T(n) = (n2) par définition.

Noter que c’est la plus grande borne inférieure qui

est recherchée.
40
 La notation Theta
Lorsque le grand-O et le grand-omega
d’une fonction coïncident, on utilise alors
la notation grand-theta.

Définition: Le temps d’exécution d’un

algorithme est dans (h(n)) s’il est à la
fois dans O(h(n)) et dans (h(n)).

41
 Notation -
• Relation d’équivalence
• Définition formelle : f(n) = (g(n)) s’il existe trois constantes
positives n0,c1 et c2 tel que c1g(n) <= f(n) <= c2g(n) pour tout n>n0

f(n) = Q (g(n))

c1 g(n)

f(n)
c2 g(n)
temps

n0 n 42
n0
 Notation (Calcul analytique)
• Étant donné deux fonctions f(n) et g(n),
f(n) = (g(n)) ssi:
  a,b > 0,  n, a <= f(n) / g(n) <= b
– limn f(n) / g(n) 
• Exemple:f(n) = 3n2+6n+4 et g(n) = n2+3
limn f(n) / g(n) = 
 3n2+6n+4 est (n2+3)
3n2+6n+4 est (n2)
– Autre propriété:
43
– f(n) = (g(n)) ssi f(n) = O(g(n)) et f(n) = (g(n))
Règles de simplification 1

Si
f(n) = O(g(n))
et
g(n) = O(h(n)),
alors
f(n) = O(h(n)).

La notation O est transitive

44
Règles de simplification 2

Si
f(n) = O(kg(n))
où k > 0, une constante
alors
f(n) = O(g(n)).
Les constantes sont ignorées

45
 Règles de simplification 3
Si
f1(n) = O(g1(n))
et
f2(n) = O(g2(n)),
alors
(f1 + f2)(n) = O(max(g1(n), g2(n)))

(f1 + f2)(n) = O(g1(n)+g2(n)))

46
Règles de simplification 4

Si
f1(n) = O(g1(n))
et
f2(n) = O(g2(n))

alors
f1(n)f2(n) = O(g1(n) g2(n))
47
Règles pour dériver la complexité
d’un algorithme
• Règle 1: la complexité d’un ensemble
d’instructions est la somme des complexités
de chacune d’elles.
• Règle 2: Les opérations élémentaires telles
que l’affectation, test, accès à un tableau,
opérations logiques et arithmétiques, lecture
ou écriture d’une variable simple ... etc,
sont en O(1)
48
• Règle 3: Instruction if: maximum entre
le bloc d’instructions de then et celui
de else

switch: prendre le maximum parmi les

complexités des blocs d’instructions des
différents cas de cette instruction.

49
Règle 4: Instructions de répétition:
1. la complexité de la boucle for est calculée par la
complexité du corps de cette boucle multipliée par le
nombre de fois qu’elle est répétée.

2. En règle générale, pour déterminer la complexité

d’une boucle while, il faudra avant tout déterminer le
nombre de fois que cette boucle est répétée, ensuite
le multiplier par la complexité du corps de cette
boucle.

50
Règle 5: Procédure et fonction: leur complexité est
déterminée par celui de leur corps.

Notons qu’on fait 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.

51
Pour les fonctions non récursives, leur
complexité temporelle se calcule en sachant
que l’appel à une fonction prend un temps
constant en O(1)

52
 Exemples
Exemple 1: a = b;
Temps constant: (1).

Exemple 2:
somme := 0;
Pour i:=1 à n
Faire
somme:= somme+n;
Fait;
Temps: (n)
53
 Exemples
Exemple 3:
somme := 0;
Pour j:=1 à n
Faire
Pour i:=1 à n
Faire
somme:=Somme +1;
Fait;
F it;
Pour k:=1 à n
Faire
A[k]:= k;
Fait;
Temps: (1) + (n2) + (n) = (n2)
54
 Exemples
Example 4:
somme := 0;
Pour i:=1 à n
Faire
Pour j:=1 à I
Faire
somme:=somme+ 1;
Fait;
Fait;

Temps: O(1) + O(n2) = O(n2)

55
 Efficacité des algorithmes
• Définition: Un algorithme est dit efficace si sa complexité
(temporelle) asymptotique est dans O(P(n)) où P(n) est un
polynôme et n la taille des données du problème considéré.

• Définition: On dit qu’un algorithme A est meilleur qu’un

algorithme B si et seulement si:

et:
t ( n )  O (t ( n )); et
A B

Où tB (etn)  O(sont
t A (n))
les complexités des algorithmes A
ettB,(n
respectivement.
) t B (n)
A

56
 Comparaison de fonctions

• En comparant deux fonctions f et

g, en termes d’ordre, il est
souvent préférable d’utiliser cette
autre définition de la notation O.
• Posons
 
f ( n)
L  lim
n  g ( n)

60
1. Si L = constante  0, alors f et g sont de
même ordre, c’est-à-dire que f(n) = O(g(n))
et g(n) = O(f(n)) ou tout simplement
O(f(n)) = O(g(n)).
2. Si L = 0 alors f est de l’ordre de g, c’est-à-
dire f(n) = O(g(n)).
3. Si L =  alors g est de l’ordre de f,
c’est-à-dire g(n) = O(f(n)).
 
61
Remarque: dans plusieurs cas, pour faciliter
les calculs, la règle suivante de l’Hôpital
est souvent utilisée. Cette règle est pratique
car, en général, la dérivée d’une fonction
est facile à évaluer que la fonction elle-même:
f ( n) f ' ( n)
lim  lim '
n  g ( n ) n g ( n)
 
 Lire: limite quand n tend vers l’infini, le rapport
des deux fonction est égal au rapport des leur
première dérivée
62
 Analyse d’algorithmes
non récursifs: quelques exemples

63
 1. Produit de deux matrices
Produit de deux matrices A(n,p) et B(p,m); on obtient
l’algorithme suivant:
Procédure multiplier (Entrée A: Tableau [n,p] de réel, B: Tableau[p,m]
de réel; sortie C: Tableau[n,m] de réel);
Début
Pour i:= 1 à n
Faire
Pour j:=1 à m
Faire
C[i,j] := 0;
Pour k:=1 à p
Faire
C[i,j] = C[i,j] + A[i,k]*B[k,j];
Fait;
Fait;
Fait;
Fin; /* fin de la fonction */ 64
Analyse: le corps de la boucle sur k est en O(1) car
ne contenant qu’un nombre constant d’opérations
élémentaires. Comme cette boucle est itérée p
fois, sa complexité est alors en O(p). La boucle sur
j est itérée m fois. Sa complexité est donc en
m.O(p) = O(mp). La boucle sur i est répétée n fois.
Par conséquent, la complexité de tout l’algorithme
est en O(nmp).

Noter que dans ce cas, il n’y pas lieu de distinguer

les différentes complexités. Dans tous les cas,
nous aurons à effectuer ce nombre d’opérations.

65
 2. Impression des chiffres
composant un nombre
Le problème consiste à déterminer les chiffres
composant un nombre donné. Par exemple, le
nombre 123 est composé des chiffres 1, 2 et 3.
Pour les trouver, on procède par des divisions
successives par 10. A chaque fois, le reste de la
division génère un chiffre. Ce processus est répété
tant que le quotient de la division courante est
différent de zéro.

66
• Par exemple, pour 123, on le divise par 10,
on obtient le quotient de 12 et un reste de 3
(premier chiffre trouvé); ensuite, on divise
12 par 10, et on obtient un reste de 2
(deuxième chiffre trouvé) et un quotient de
1. Ensuite, on divise 1 par 10; on obtient un
reste de 1 (troisième chiffre trouvé) et un
quotient de zéro. Et on arrête là ce
processus.

67
L’algorithme pourrait être comme suit:
Procédure Chiffres(Entrée n: entier);
Début
Var quotient, r: Entier;
quotient := Div(n,10);
Tantque (quotient >= 10)
Faire
r := Reste(n,10);
Ecrire(r);
n := quotient;
quotient := Div(n,10);
Fait;
r := Reste (n,10);
Ecrire(r);
Fin;/* fin de la procédure
Analyse: Comme le corps de la boucle ne contient qu’un nombre
constant d’instructions élémentaires, sa complexité est en O(1). Le
problème consiste à trouver combien de fois la boucle while est
répétée. Une fois cette information connue, la complexité de tout
l’algorithme est facile à dériver. Déterminons donc ce nombre. Soit k
l’itération k. Nous avons ce qui suit:

itération k 1 2 3 ...... k

valeur de n n/10 n/102 ……. n/10k

Donc, à l’itération k, la valeur courante de n est de n/10 à la puissance k

69
Or, d’après l’algoithme, ce processus va s’arrêter dès que
n/10puissance k < 10
Autrement dit, dès que
n < 10à la puissance (k+1)
En passant par le log,
k + 1> log n
Autrement dit, le nombre d’itérations effectuées est
k = O(log n)
Par conséquent, la complexité de l’algorithme ci-dessus est
en O(log n).

70
 3. PGCD de deux nombres
Nous avons déjà vu que l’algorithme est comme suit:

Fonction PGCD (Entrée A, B: entier):entier

Début
Var
reste : entier;
reste := A Mod B;
Tantque (reste <> 0)
Faire
A:= B;
B:= reste;
reste: = A Mod B;
Fait;
PGCD:=B;
Fin; /* fin de la fonction */ 71
Analyse: Encore une fois, le gros problème consiste à
déterminer le nombre de fois que la boucle Tantque est
répétée. Il est clair que dans ce cas, il y a lieu normalement
de distinguer les trois complexités. En ce qui nous concerne,
nous allons nous limiter à celle du pire cas. Pour ce qui est
de celle du meilleur cas, elle est facile à déterminer; mais,
en revanche, celle du cas moyen, elle est plus compliquée et
nécessite beaucoup d’outils mathématique qui sont en
dehors de ce cours.

Pour ce faire, procédons comme suit pour la complexité dans le

pire cas:

72
 Analyse PGCD suite
Avant tout, nous avons besoin du résultat suivant:

Proposition : Si reste = n mod m alors reste < n/2

Preuve: Par définition, nous avons:

Donc reste = n –q.m; q >=1

 reste <= n –m (1)
On sait aussi que reste <= m -1 (2)
En additionnant (1) avec (2), on obtient:
2 reste <= n – 1
donc: reste < n / 2 CQFD

73
 PGCD Suite
• Durant les itérations de la boucle Tantque, l’algorithme génère, à
travers la variable reste, la suite de nombres {r0, r1, r2, r3 , ... },
représentant les valeurs que prennent les variables n et m, où

r0  n; r1  m;
r j précédente,
De la proposition 1  r j 1onmod rj ; j  2
peut déduire

r j 1  r j 1 / 2
Par induction sur j, on obtient l’une des deux relation suivantes, selon
la parité de l’indice j:

74
 PGCD suite
r< r /2
j 0 j/2
si j est pair
r < r / (2
j 0 (j-1)/2
si j est impair

Dans les deux cas, la relation suivante est vérifiée:

rj < max(n,m) / (2j/2))

75
Dès que rj < 1, la boucle while se termine, c’est-à-
dire dès que:

2j/2 = max(n,m) +1

76
Par conséquent, le nombre de fois que la boucle
Tantque est répétée est égal à

2log(max(n,m)+1) = O(log max(n,m)).

Comme le corps de cette boucle est en O(1), alors la

complexité de tout l’algorithme est aussi en
O(log max(n,m))

77
 4. Recherche d’un élément dans un tableau trié
Nous avons déjà vu ce problème. Son algorithme est comme suit:

Fonction recherche2(Entrée tab: Tableau[n] entier; C: entier): Entier;

Début
Var
sup, inf, milieu: Entier;
trouve: Booléen;
inf := 1; sup :=n; trouve := faux;
Tantque (sup >=inf et non trouve)
Faire
milieu = [(inf + sup) / 2];
Si (C = tab[milieu]) Alors trouve :=Vrai;
Sinon
Si (C < tab[milieu])
Alors sup := milieu -1;
Sinon inf := milieu + 1;
Fsi;
Fsi;
Fait;
Si (non trouve) Alors Recherche2:=-1;
Sinon Recherche2:= milieu;
Fsi;
Fin; /* fin de la fonction */

78
Analyse: comme nous l’avons déjà mentionné précédement,
il y a lieu de distinguer entre les trois différentes
complexités.
Meilleur cas: Il n’est pas difficile de voir que le cas
favorable se présente quand la valeur recherchée C est
au milieu du tableau. Autrement dit, la boucle Tantque
ne sera itérée qu’une seule fois. Dans ce cas,
l’algorithme aura effectué un nombre constant
d’opérations; c’est-à-dire en O(1).

79
• Pire cas: Ce cas se présente quand l’élément C
n’existe pas. Dans ce cas, la boucle Tantque sera
itérée jusqu’à ce que la variable sup < inf. Le
problème est de savoir combien d’itérations sont
nécessaires pour que cette condition soit vérifiée.
Pour le savoir, il suffit de constater, qu’après
chaque itération, l’ensemble de recherche est
divisé par deux. Au départ, cet intervalle est égal à
sup (= n) – inf (= 1) + 1 = n.

80
Itération intervalle de recherche
0 n
1 n/2
2 n/4
3 n/8
................................................
k n/2k

81
On arrêtera les itérations de la boucle Tantque
dès que la condition suivante est vérifiée

n/2k = 1  k = O(log n)

Autrement dit, la complexité de cet

algorithme dans le pire cas est en O(log n).

82