Recherche linéaire vs dichotomique
Recherche linéaire vs dichotomique est une expérience interactive de Algorithmes en action, une simulation gratuite de StudyFi Lab qui fonctionne directement dans le navigateur.
La recherche linéaire examine les éléments un par un, donc dans le pire cas il faut n étapes : O(n). La recherche dichotomique ne marche que sur un tableau trié : elle regarde au milieu et, selon le résultat, élimine toute une moitié. Après chaque étape il reste au plus la moitié, donc ⌈log₂(n+1)⌉ étapes au plus suffisent : O(log n). Pour 40 éléments, c’est 6 étapes au lieu de 40.
Essaie ceci: Mets 40 éléments et cherche la dernière valeur. Choisis ensuite un nombre absent du tableau : combien d’étapes faut-il à chaque recherche pour s’en rendre compte ?
Questions fréquentes
Que montre l’expérience « Recherche linéaire vs dichotomique » ?
La recherche linéaire examine les éléments un par un, donc dans le pire cas il faut n étapes : O(n). La recherche dichotomique ne marche que sur un tableau trié : elle regarde au milieu et, selon le résultat, élimine toute une moitié. Après chaque étape il reste au plus la moitié, donc ⌈log₂(n+1)⌉ étapes au plus suffisent : O(log n). Pour 40 éléments, c’est 6 étapes au lieu de 40.
Comment essayer « Recherche linéaire vs dichotomique » ?
Mets 40 éléments et cherche la dernière valeur. Choisis ensuite un nombre absent du tableau : combien d’étapes faut-il à chaque recherche pour s’en rendre compte ?
Tu révises pour un contrôle ?
Importe tes notes et StudyFi les transforme en fiches, tests et podcasts.