1
Est-ce O (n log n) ou O (log n)?Quelle est la complexité d'une liste circulaire à double liaison utilisant la recherche binaire?
A
Répondre
4
Je vais dire que ce n'est pas O (log n) car les recherches binaires ne fonctionnent pas bien sur les listes chaînées - vous n'avez pas un accès aléatoire efficace.
Si vous avez vraiment essayé de faire une recherche binaire, cela prendrait des étapes O (log n), mais à chaque étape, vous avez besoin d'une traversée O (n) pour accéder à l'élément désiré. Donc vous pouvez dire que c'est O (nlog (n)).
Vous devriez simplement faire une recherche linéaire O (n) à la place.
+2
Vous n'avez * aucun * accès aléatoire; tout l'accès est linéaire. Mais, oui, je suis d'accord avec votre réponse. –
0
La recherche binaire nécessite un accès aléatoire, ce qui n'est pas possible dans une liste chaînée. Vous êtes bloqué avec une recherche linéaire O (n).
Questions connexes
- 1. Quelle est la complexité d'exécution des fonctions de liste Python?
- 2. Recherche binaire d'une liste C# en utilisant la condition déléguée
- 3. Quelle implémentation de la file circulaire est la meilleure?
- 4. Quelle est la complexité de la concaténation des cordes équilibrées?
- 5. Plus rapide que la recherche binaire pour la liste ordonnée
- 6. Quelle est la complexité de ce genre spécialisé
- 7. Effacement d'une liste à double liaison
- 8. Quelle est la complexité temporelle de LinkedList.getLast() en Java?
- 9. Quelle est la complexité temporelle de l'éclatement des éléments de la liste en Python?
- 10. liste de liaison de double avec la culture invariante
- 11. Quelle est la complexité temporelle de l'indexeur DataRow?
- 12. Quelle est la complexité de hash_set :: size() dans C++ STL?
- 13. Quelle est la complexité temporelle de l'itération de TreeSet?
- 14. Quelle liaison WCF est la plus performante?
- 15. convertir la valeur double en valeur binaire
- 16. Recherche binaire dans la matrice 2D
- 17. Quelle est la meilleure approche de recherche?
- 18. Quelle est la complexité du code ci-dessous par rapport à la mémoire?
- 19. Quelle est la différence entre la liaison XML de Castor et la liaison JAXB
- 20. Empêcher la référence circulaire
- 21. Ajout d'un noeud dans une liste à double liaison
- 22. erreur: opérandes invalides à% binaire (ont 'double' et 'double')
- 23. Implémenter la recherche binaire dans les objets
- 24. Comment afficher la représentation binaire d'un float ou d'un double?
- 25. ComboBox.SelectedValue est foiré après la liaison à une liste
- 26. liste stl - complexité
- 27. Quelle est la meilleure méthode pour lire un double à partir d'un fichier binaire créé en C?
- 28. Quelle est la meilleure façon d'implémenter le versioning d'un binaire?
- 29. liaison dateGridView colonne à la liste
- 30. TreeMap - Complexité du temps de recherche
@Frustrated - Pourquoi avez-vous tagué ceci avec «devoirs»? Saif dit [ici] (http://stackoverflow.com/questions/2326831/a-list-of-java-errors-and-warnings/2326876#2326876) qu'il développe une traduction de Java en arabe, pas exactement un étudiant Tâche de niveau –
@reemrevnivek: Je l'ai étiqueté 'devoirs 'parce qu'il ressemble beaucoup à une question de devoirs: pas de contexte du problème, pas d'explication de * pourquoi * il veut faire une recherche binaire en utilisant une liste circulaire doublement chaînée, et il * regarde * Comme les questions de devoirs que j'avais reçus et vu d'autres recevoir. @Saif: Désolé si ce n'était pas des devoirs, mais il en avait l'apparence. – FrustratedWithFormsDesigner
@Frustrated: c'est bien. En fait j'étais curieux et je n'y pensais pas, on m'avait déjà enseigné (pas un devoir cependant: P) que c'était inefficace mais je pensais pourquoi serait-ce si j'avais utilisé des pointeurs cachés, mon mal pour ne pas y penser? bien que. – Saif