Discussion :

[Oberown]

Quel est le meilleur algorithme utilisé pour faire la recherche d'un élèment dans une liste non trié ?

[Higgins]

Dans une liste non triée, tu es obligé de la parcourir entièrement puis qu'aucun élément ne te permet d'être sûr que l'objet recherché n'existe pas plus loin.

[nako]

bon la liste n'est pas triée ...
tu n'as pas d'infos supplémentaires sur ta liste ?
si non, alors tu prends un à un les éléments de ta liste et tu t'arrêtes quand tu as trouvé l'élément cherché ...
je vois que ça.

[Nemerle]

Si ta question veut dire quel est le meilleur algo pour trouver statistiquement le plus vite possible un element dans un paquet, la réponse est.... aléatoirement (sisi, c'est vrai).

Maintenant, l'aléatoirement n'est bien sur pas acceptable (le risque de passer 100 ans avant de trouver ), et donc fais-le séquentiellement.

Mais l'aléatoire reste le meilleur algo.

[alex00]

Dans une structure séquentielle, tu ne peux que faire un parcours séquentiel.

La recherche d'un élément parmi n : 0(n)

Si tu as plusieurs recherches à faire :
rechercher m éléments dans une liste ne n éléments : O(m*n)

Dès que tu as quelques recherches à faire, tu peux :
créer un vecteur de pointeurs sur chaque élément de la liste : O(n)
trier le vecteur (quick sort) : O(n*log(n))
faire les m recherches : O(m*log(n))
=> O(n) + O((n+m)*log(n))
=> ce qui est en log(n) est négligeable : O(n)

[Nemerle]

alex00>> tu viens de prouver qu'une recherche séquentielle à une complexité linéaire!!

Etonnant, non??

[Selenite]

Mais l'aléatoire reste le meilleur algo.

Le meilleur algo théorique. Un tel algo nécessite une source de nombres aléatoires parfaite. Chacun sait qu'une telle source est très dure à obtenir en informatique.

Ensuite, la liste étant non triée, on peut conjecturer qu'elle est ranger aléatoirement. Si tel est effectivement le cas, alors la recherche peut se faire linéairement en gardant un temps moyen constant tout comme avec l'algo aléatoire cité ci-dessus.

En revanche si la liste n'est pas ranger aléatoirement, alors l'algo aléatoire redevient théoriquement le meillleur dans le sens où son temps moyen de recherche est constant.

L'algo aléatoire peut être amélioré et devenir réellement intéressant si on ne tire pas les nombres en jetant un dé, mais en piochant de cartes. C'est-à-dire en empèchant de tirer plusieurs fois le même nombre.

[Nemerle]

et il suffit d'implémenter un générateur super-astronomique de type mersenne twister par exemple pour obtenir des nombres aléatoires "satisfaisant"