Intermédiaire
🧠 Fondamentaux
20 XP
0 personnes ont réussi
Complexité O(log n) — recherche dichotomique
O(log n), c'est la complexité logarithmique. C'est tres rapide : meme si ta liste a un million d'éléments, il te faut seulement environ 20 étapes.
Le principe est simple : a chaque étape, tu divises ton espace de recherche par 2. C'est exactement ce que tu fais quand tu cherches un mot dans un dictionnaire papier. Tu ouvres au milieu, tu regardes si le mot est avant ou apres, et tu recommences dans la moitie qui t'interesse.
Pour une liste de taille 8 : 8 -> 4 -> 2 -> 1, soit 3 étapes. Pour une liste de taille 16 : 16 -> 8 -> 4 -> 2 -> 1, soit 4 étapes.
Mathematiquement, c'est le logarithme en base 2, arrondi au dessus.
Écris une fonction compter_etapes_dichotomie(n) qui retourne le nombre d'étapes nécessaires pour trouver un élément dans une liste triee de taille n.