Livre_silo 30 août 2013 16:32 Page 158
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
158
Informatique pour tous
On veut maintenant montrer que la complexité de cet algorithme est au pire O(log n) où
n est la longueur du tableau. En particulier, on effectue au pire un nombre logarithmique
de comparaisons. La démonstration consiste à établir qu’après k itérations de la boucle,
on a l’inégalité suivante :
d − g <
n
2 k ·
La démonstration se fait par récurrence sur k. Initialement, on a g = 0 et d = n − 1 et
k = 0, donc l’inégalité est établie. On suppose maintenant l’inégalité vraie au rang k et
g ⩽ d. À la fin de la k + 1-ième itération, on a soit g = m+1, soit d = m-1. Dans le premier
cas, on a donc :
d −
(⌊
g + d
2
⌋
+ 1
)
⩽ d −
g + d
2
=
d − g
2
<
n
2 k × 2
=
n
2 k+1 ·
Le second cas est laissé au lecteur. On conclut ainsi : pour k ⩾ log 2 (n), on a d − g < 1,
c’est-à-dire d − g ⩽ 0. On fait alors au plus une dernière itération.
La complexité de la recherche dichotomique est donc O(log n), alors que celle de la recherche séquentielle est O(n). Il ne faut cependant pas oublier qu’elles ne s’appliquent pas
dans les mêmes conditions : une recherche dichotomique est exclue si les données ne sont
pas triées.
Exercice 6.8 Écrire une fonction qui renvoie l’élément maximal d’un tableau d’entiers. On discutera des
diverses solutions possibles pour traiter le cas d’un tableau de longueur 0.
Exercice 6.9 * Écrire une fonction qui renvoie les deux plus grands éléments d’un tableau d’entiers. On
supposera que le tableau est de longueur au moins 2 ; en revanche, on veillera à ne le parcourir qu’une
seule fois.
Exercice 6.10
1 Écrire une fonction qui renvoie l’indice de la première occurrence de l’élément maximal d’un tableau
d’entiers.
2 Évaluer la complexité de cette fonction.
3 Démontrer que tout algorithme répondant à cette question a une complexité au moins linéaire.
6.4 Recherche d’un mot dans un texte
Un problème classique en informatique consiste à rechercher, non pas une seule valeur,
mais une séquence de valeurs dans un tableau. Cela revient à chercher une occurrence d’un
tableau dans un autre ou, pour les chaînes de caractères, une occurrence d’un mot dans un
texte. On souhaite donc écrire une fonction recherche_mot qui, étant donnés deux tableaux
m et t, détermine la position de la première occurrence de m dans t, si elle existe, et qui
renvoie None sinon. Ainsi, pour les tableaux m=[1,2,3] et t=[2,1,4,1,2,6,1,2,3,7], recherche_mot
renvoie 6 :
[2, 1, 4, 1, 2, 6, 1, 2, 3, 7]
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
158
Informatique pour tous
On veut maintenant montrer que la complexité de cet algorithme est au pire O(log n) où
n est la longueur du tableau. En particulier, on effectue au pire un nombre logarithmique
de comparaisons. La démonstration consiste à établir qu’après k itérations de la boucle,
on a l’inégalité suivante :
d − g <
n
2 k ·
La démonstration se fait par récurrence sur k. Initialement, on a g = 0 et d = n − 1 et
k = 0, donc l’inégalité est établie. On suppose maintenant l’inégalité vraie au rang k et
g ⩽ d. À la fin de la k + 1-ième itération, on a soit g = m+1, soit d = m-1. Dans le premier
cas, on a donc :
d −
(⌊
g + d
2
⌋
+ 1
)
⩽ d −
g + d
2
=
d − g
2
<
n
2 k × 2
=
n
2 k+1 ·
Le second cas est laissé au lecteur. On conclut ainsi : pour k ⩾ log 2 (n), on a d − g < 1,
c’est-à-dire d − g ⩽ 0. On fait alors au plus une dernière itération.
La complexité de la recherche dichotomique est donc O(log n), alors que celle de la recherche séquentielle est O(n). Il ne faut cependant pas oublier qu’elles ne s’appliquent pas
dans les mêmes conditions : une recherche dichotomique est exclue si les données ne sont
pas triées.
Exercice 6.8 Écrire une fonction qui renvoie l’élément maximal d’un tableau d’entiers. On discutera des
diverses solutions possibles pour traiter le cas d’un tableau de longueur 0.
Exercice 6.9 * Écrire une fonction qui renvoie les deux plus grands éléments d’un tableau d’entiers. On
supposera que le tableau est de longueur au moins 2 ; en revanche, on veillera à ne le parcourir qu’une
seule fois.
Exercice 6.10
1 Écrire une fonction qui renvoie l’indice de la première occurrence de l’élément maximal d’un tableau
d’entiers.
2 Évaluer la complexité de cette fonction.
3 Démontrer que tout algorithme répondant à cette question a une complexité au moins linéaire.
6.4 Recherche d’un mot dans un texte
Un problème classique en informatique consiste à rechercher, non pas une seule valeur,
mais une séquence de valeurs dans un tableau. Cela revient à chercher une occurrence d’un
tableau dans un autre ou, pour les chaînes de caractères, une occurrence d’un mot dans un
texte. On souhaite donc écrire une fonction recherche_mot qui, étant donnés deux tableaux
m et t, détermine la position de la première occurrence de m dans t, si elle existe, et qui
renvoie None sinon. Ainsi, pour les tableaux m=[1,2,3] et t=[2,1,4,1,2,6,1,2,3,7], recherche_mot
renvoie 6 :
[2, 1, 4, 1, 2, 6, 1, 2, 3, 7]