Algorithme de recherche séquentiel
Résolu
Bonsoir pour tt le monde,
s'ils vous plais
quel est la complexité de l'algorithme de recherche sequentiel d'un element ds une list de n elements
s'ils vous plais
quel est la complexité de l'algorithme de recherche sequentiel d'un element ds une list de n elements
Configuration: Windows Internet Explorer 7.0
2 réponses
-
Sur une liste à n éléments tu parcours dans le pire cas n éléments. Donc O(n).
http://fr.wikipedia.org/wiki/Théorie_de_la_complexité_des_algorithmes
Selon la structure de donnée la complexité est plus ou moins bonne. Par exemple dans un structure d'arbre binaire équilibré dans lequel les éléments sont ordonnés (arbre rouge noir) la complexité pour chercher un élément serait O(log(n)) ce qui est tout de suite beaucoup plus performant.
https://fr.wikipedia.org/wiki/Arbre_bicolore
Ci-dessous la complexité des structures C++ de la STL :
https://forums.commentcamarche.net/forum/affich-37604421-introduction-a-la-stl-en-c-standard-template-library
Bonne chance -
De rien et bonne continuation :-)
