9
Quel est le coût/complexité d'un String.indexOf() fonction d'appelQuel est le coût/complexité d'un appel de fonction String.indexOf()
A
Répondre
0
En java, si l'appel est string1.indexOf (string2) le coût en temps serait O (m - n) où m est la longueur de string1 et n est la longueur de string2.
9
la mise en œuvre IIRC Java de .indexOf() est juste le naive string matching algorithm, qui est O(n+m) moyenne et O(n*m) pire des cas.
En pratique, c'est assez rapide; Je l'ai testé pour des chaînes d'aiguilles relativement grandes (> 500 char) et de haystack (quelques MB) et il ferait l'appariement en moins d'une seconde (dans un ordinateur domestique moyen). Rappelez-vous que je l'ai forcé à traverser toute la meule de foin.
+0
Je sais que c'est il y a longtemps, mais savez-vous d'où vous venez? J'aurais besoin de cette information pour ma thèse de baccalauréat et je ne sais pas si Stackoverflow serait une référence acceptable pour une thèse;) – odaa
+0
@odaa J'ai fait quelques expériences et j'ai écrit un article là-dessus quand j'étais au collège. – NullUserException
+0
@NullUserException, Pourquoi dites-vous que 'O (n + m)' est le cas moyen? http://stackoverflow.com/a/12752295/632951 semble contredire ce point. – Pacerier
0
Dépend de l'implémentation. Par exemple, lors de la recherche d'une chaîne dans une chaîne plus longue, "L'algorithme Turbo Boyer-Moore prend une quantité d'espace constante supplémentaire pour effectuer une recherche dans 2n comparaisons (par opposition à 3n pour Boyer-Moore), où n est le nombre de caractères dans le texte à rechercher. " (Voir Wikipedia).
+1
@caleb: Vraiment, comment pouvez-vous dire à partir de la question? –
Questions connexes
- 1. Fonction String.indexOf dans C
- 2. API Java String.indexOf
- 3. Quel est le meilleur moyen d'envoyer QStrings dans un appel de fonction?
- 4. C#: String.IndexOf à FileStream.Seek
- 5. Quel est le problème avec cette fonction?
- 6. Quel est le problème avec ma fonction?
- 7. Quel est le problème avec cette fonction?
- 8. Appel d'une fonction sur n'importe quel événement de textarea
- 9. JSF - Appel Ajax - Quel est le problème sur ce code?
- 10. jQuery: Quel est le problème avec cet appel jQuery.css()?
- 11. Quel est le danger en augmentant simplement le pool de connexion?
- 12. Quel est le nom officiel de cette fonction de syntaxe?
- 13. Quel est le contraire de la fonction localtime dans Perl?
- 14. Quel est le but de la fonction en php crc
- 15. Quel est le synonyme de cette fonction dans obj-c?
- 16. Quel est le contraire de la fonction PHP date()?
- 17. Quel est le problème avec cette fonction de jquery?
- 18. Haskell: Quel est le type de cette fonction?
- 19. Appel d'une fonction qui est un attribut
- 20. Appel de fonction minuté
- 21. Ajax appel de fonction
- 22. Quel est le bon cas de test pour trouver quel appel de méthode est plus rapide entre execute et getElementsByTagName?
- 23. Appel de fonction d'imbrication
- 24. Appel d'une fonction qui est déclarée dans la fonction actuelle
- 25. Bouclage en fonction ou appel multiple de la fonction, qu'est-ce qui est le plus rapide?
- 26. Quel est le nombre maximal d'arguments dans une fonction Python?
- 27. quel est le meilleur moyen d'écrire une fonction php mysql?
- 28. Quel est le point dans la fonction d'abandon en JavaScript?
- 29. Quel est le problème avec la fonction MySQL DATE()?
- 30. Quel est le problème avec ma fonction d'animation?
Dans quelle langue, et par rapport à quoi? Quels sont les arguments de la fonction - faut-il une chaîne, un caractère, un comparateur personnalisé? – Kobi
Est-ce Java dont vous parlez? – NullUserException
copie de http://stackoverflow.com/questions/12752274/java-indexofstring-str-method-complexity –