Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

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



  1. #1
    CompositeStructure

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


    ------

    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(log2n). 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 log2n ? 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

    -----
    Dernière modification par CompositeStructure ; 28/08/2020 à 16h05.

  2. Publicité
  3. #2
    CompositeStructure

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

    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

  4. #3
    gg0
    Animateur Mathématiques

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

    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 log2 est le logarithme binaire (logarithme de base 2) :


    Cordialement.

  5. #4
    Paraboloide_Hyperbolique

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

    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.

  6. A voir en vidéo sur Futura
  7. #5
    CompositeStructure

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

    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

Discussions similaires

  1. Complexité d'un algorithme
    Par e5mm100 dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 10/06/2020, 14h28
  2. complexité d'un algorithme recursif
    Par bmce dans le forum Programmation et langages, Algorithmique
    Réponses: 5
    Dernier message: 08/12/2016, 06h25
  3. preuve et complexite algorithme
    Par tlop dans le forum Programmation et langages, Algorithmique
    Réponses: 0
    Dernier message: 26/10/2016, 23h41
  4. Complexité de l'algorithme de Shor
    Par Argyre dans le forum Discussions scientifiques
    Réponses: 14
    Dernier message: 19/11/2009, 18h26
  5. Complexité d'algorithme
    Par natachaSt dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 23/12/2006, 22h00