Nombre d'opérations

Exercice 1

On reprend la notation p(n) pour le nombre de passages au pire dans la boucle lors d'une recherche dichotomique dans une liste de taille n.

Expliquer pourquoi p(n) est de l'ordre de blog(n).

Des arguments

n est compris entre deux puissances de 2: $2^k \leqslant n < 2^{k+1}$ (et k = blog(n)).

On a donc $\frac{n}{2^{k+1}} < 1$.

Comme à chaque étape, on divise la taille de liste dans laquelle on cherche par environ 2, on voit qu'en blog(n)+1 étapes, la liste sera de taille 0 et la recherche terminée.

A retenir

Le nombre au pire de passages dans la boucle lors d'une recherche dichotomique dans une liste de taille n est approximativement blog(n).

On rappelle que le nombre de bits dans l'écriture binaire d'un entier n est blog(n)+1. On peut donc retenir que le nombre au pire de passages dans la boucle est approximativement le nombre de bits dans l'écriture binaire de n.

Exercice 2

Expliciter un exemple de liste de taille n et de valeur cherchée nécessitant exactement blog(n)+1 passages dans la boucle.

Aide

Prenez l'exemple d'une liste de longueur n = 8: L = [x₀, x₁, x₂, x₃, x₄, x₅, x₆, x₇]. et cherchez une valeur v strictement plus grande que toute valeur de cette liste.

Réponse

Prenons l'exemple d'une liste de longueur n = 8: L = [x₀, x₁, x₂, x₃, x₄, x₅, x₆, x₇]. et cherchons une valeur v strictement plus grande que toute valeur de cette liste.

On a blog(8) + 1 = blog(2³) + 1 = 4.

Avant la boucle, gauche = 0, droite = 7, centre = 3.

• Etape 1.
  On entre dans la boucle: gauche = 4, droite = 7 puis centre = 5.
• Etape 2.
  gauche = 6, droite = 7 puis centre = 6.
• Etape 3.
  gauche = 7, droite = 7, puis centre = 7.
• Etape 4.
  gauche = 8, droite = 7.

gauche > droite: on sort de la boucle et renvoie False.

Il a fallu blog(n)+1 étapes.

De façon plus générale, avec une liste de longueur 2^k et la recherche d'une valeur strictement plus grande que les valeurs présentes, on aura blog(n)+1 passages dans la boucle.

Exercice 3

On suppose disposer d'un annuaire de la population française, c'est à dire d'une liste d'environ 65 millions de noms. On recherche un nom. Quel est le nombre maximum de passages dans la boucle effectués dans une recherche dichotomique ?

Réponse

2²⁵ ≤ 65 000 000 < 2²⁶.

Le nombre de passages dans la boucle sera au pire d'environ 26.

On suppose disposer d'un annuaire de la population mondiale, c'est à dire d'une liste d'environ 7 milliards de noms.

• Par quel nombre faut-il multiplier la population française pour obtenir la population mondiale ?
• On recherche un nom dans l'annuaire de la population mondiale. Quel est le nombre maximum de comparaisons effectuées dans la recherche dichotomique ?

Rapport

$\frac{\text{pop mondiale}}{\text{pop française}} \approx \frac{7\times 10^9}{65\times 10^6} \approx 108$.

La population mondiale est environ 108 fois la population française.

Attention

Ne pas en déduire qu'il faut 108 fois plus de tests dans une recherche dichotomique! La recherche dichotomique est bien plus efficace que cela!

Réponse

Environ 34 passages dans la boucle dans le cas au pire (à comparer aux 7 milliards de comparaisons potentielles pour une recherche séquentielle!).

Éléments d'explication sur les écarts dans les nombres de passages

La population est multipliée par 108 et pourtant, il ne faut que 7 tests supplémentaires pour constater qu'un nom est absent de la liste. Pourquoi?

Cela est dû au fait que le nombre de tests à faire (passages dans la boucle) n'est pas proportionnel à n mais est de l'ordre de blog(n) où n est la longueur de la liste. Or, en arrondissant, la population française est environ de $2^{26}$, d'où blog(pop française) ≈ 26 et la population mondiale est environ $2^{33}$, d'où blog(pop mondiale) ≈ 33. Et 33-26 = 7.

Remarque: complexité exponentielle vs complexité logarithmique

La complexité de la recherche dichotomique est ce que l'on appelle une complexité logarithmique (nombre d'opérations de l'ordre de blog(n) pour une entrée de taille n).

Un algorithme à complexité logarithmique est un algorithme "rapide".

On pourrait "résumer" une telle complexité par la phrase simplificatrice suivante:
doubler la taille de l'entrée n'ajoute qu'une unité au temps de calcul.

Tandis qu'une complexité exponentielle (nombre d'opérations de l'ordre de 2ⁿ pour une entrée de taille n) correspond à un algorithme très lent (et même souvent inutilisable même pour des valeurs de n pas très grandes).

On pourrait "résumer" une telle complexité par la phrase simplificatrice suivante:
ajouter un à la taille de l'entrée multiplie par deux le temps de calcul.