Bonjour,
Je dois trouver un élément dans une énorme liste triée. Pourriez-vous me conseiller sur le choix de l'algorithme à utiliser? Je souhaiterais qu'il soit le plus rapide possible...
Cordialement,
Rodrigue
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
Recherche d'un élément dans une liste triée (vitesse)
Bonjour,
Je dois trouver un élément dans une énorme liste triée. Pourriez-vous me conseiller sur le choix de l'algorithme à utiliser? Je souhaiterais qu'il soit le plus rapide possible...
Cordialement,
Rodrigue
Le plus rapide que je connaisse est la recherche dichotomique puisque ta liste est triée
bon courage
Je confirme.
Il vaut mieux mobiliser son intelligence sur des conneries que mobiliser sa connerie sur des choses intelligentes --- devise SHADOKS
Kit de survie Android : mon guide pour apprendre à programmer sur Android, mon tutoriel sur les web services et enfin l'outil en ligne pour vous faire gagner du temps - N'oubliez pas de consulter la FAQ Android
Il y a encore moyen de faire mieux que la dichotomie O(n log n) en utilisant le principe des tables de hachage, mais il faut bien voir si les données triées autorisent un tel principe.
Il existe de nombreuses implémentations de tables de hachage.
La recherche dichotomique est de O(log n) puisque tu divises toujours par deux la longueur du tableau par (environ) deux à chaque traitement.Envoyé par Charlemagne
Sorry, j'ai écris trop vite, j'ai confondu avec la FFT ;-)
O(n log n) aurait éte encore plus lent qu'une recherche sur tous les éléments !!
Effectivement c'est O(log n)
Avec un peu de chance c'est O(1) avec une bonne table de hachage
Répondre avec citation
Partager