Complexité d'un algorithme - binary search O(log2(n))

[CompositeStructure]

Bonjour,

Je suis en train d'étudier de mon côté pour le BTS les algorithmes.
J'essaye de comprendre comment on évalue "l'efficacité" d'un algo et je suis tombé sur grand O de n, noté O(n) ou teta(n).

Je suis en train de voir l'algorithme binary search où l'on cherche une valeur en réalisant des divisions successives du milieu de l'intervalle et en réduisant l'intervalle à la partie contenant la valeur recherchée. Je ne comprends pas pourquoi la complexité de cet algorithme est de type logarithme décimal. Le résultat est O(log₂n). J'ai eu beau cherché je ne comprends pourquoi, cela doit peut-être du au fait que l'on réalise une division par 2, il y a sûrement un point de mathématique que je comprends pas, ou que j'ai tout simplement oublié.
D'autre part que représente le 2 dans log₂n ? Ce que je me rappelle c'est que log x = ln x / ln 10 et que exp ln x = a.

J'ai écris le pseudo-code dans le lien ci-dessous pour garder la syntaxe afin de faciliter la lecture.

https://pastebin.com/4B74WtrQ

Merci beaucoup par avance

Cordialement

Mathieu
-----

[CompositeStructure]

Une explication sur les variables:

A[9] : entier # vecteur de taille 10 contenant les valeurs
T : entier # valeur recherchée
L : entier # borne de gauche
R : entier # borne de droite
m : entier # index qui balaye le vecteur
trouve : booléen # valeur trouvée ou non

[gg0]

Bonjour.

Pour "comprendre" la complexité d'un algorithme, il faut faire le calcul. Il n'y a rien d'intuitif dans ce genre de question, sauf pour des algorithmes très simples.
Le log₂ est le logarithme binaire (logarithme de base 2) :


Cordialement.

[Paraboloide_Hyperbolique]

Bonjour,

L'algorithme fonctionne en divisant, chaque itération, par deux la longueur de l'intervalle dans lequel se trouve la valeur recherchée. Mettons, sans perte de généralité*, qu'une valeur inconnue x est à rechercher dans l'intervalle [0, 1].

Au départ l'intervalle est de longueur 1.

A l'itération 1, x se trouve soit dans [0, 1/2], soit ]1/2, 1[; tous deux de longueur 1/2.
A l'itération 2, x se trouve dans [0, 1/4[ ou [1/4, 2/4[, ou [2/4, 3/4[, ou [3/4, 1]; tous de longueur 1/4.

En continuant ainsi, à l'itération n, x sera localisé dans un intervalle de longueur , c'est-à-dire que l'on connaîtra sa valeur exacte à près après n itérations.

*Sinon, il suffit de translater et de mettre à l'échelle l'intervalle de départ pour retomber sur [0, 1] au moyen d'une simple transformation linéaire.

[A voir en vidéo sur Futura]

[CompositeStructure]

Bonjour,

Désolé de ne pas avoir répondu plus tôt.

Merci pour vos retours.

J'ai compris grâce à ton exemple Paraboloide_Hyperbolique

Merci beaucoup

Cordialement

Mathieu