9
Was die Kosten/Komplexität eines String.IndexOf() FunktionsaufrufWas ist die Kosten/Komplexität eines String.IndexOf() Funktionsaufruf
A
Antwort
0
in Java ist, wenn der Anruf string1.indexOf (string2) die Zeitkosten wären O (m - n), wobei m die Länge von string1 und n die Länge von string2 ist.
9
IIRC Java-Implementierung von .indexOf() ist nur die naive string matching algorithm, das ist O(n+m) Durchschnitt und O(n*m) schlimmster Fall.
In der Praxis ist das schnell genug; Ich testete es für relativ große Nadel (> 500 Char) und Heuhaufen (einige MB) Saiten und es würde die Anpassung in unter einer Sekunde (in einem durchschnittlichen Haushaltscomputer) tun. Wohlgemerkt, ich habe es gezwungen, durch den ganzen Heuhaufen zu gehen.
+0
Ich weiß, es ist lange her, aber wissen Sie, woher Sie das haben? Ich würde diese Informationen für meine Bachelor-Thesis brauchen und ich weiß nicht, ob Stackoverflow eine akzeptable Referenz für eine Dissertation wäre;) – odaa
+0
@odaa Ich habe ein paar Experimente gemacht und ein Papier darüber geschrieben, als ich am College war. – NullUserException
+0
@NullUserException, Warum sagen Sie, dass 'O (n + m)' der durchschnittliche Fall ist? http://stackoverflow.com/a/12752295/632951 scheint diesem Punkt zu widersprechen. – Pacerier
0
Hängt von der Implementierung ab.
Wenn Sie beispielsweise nach einer Zeichenfolge innerhalb einer längeren Zeichenfolge suchen, benötigt der Turbo Boyer-Moore-Algorithmus eine zusätzliche konstante Menge an Speicherplatz, um eine Suche innerhalb von 2n Vergleichen (im Gegensatz zu 3n für Boyer-Moore) durchzuführen n ist die Anzahl der Zeichen im zu suchenden Text. " (siehe Wikipedia).
+1
@caleb: Wirklich, wie kannst du von der Frage erzählen? –
Verwandte Themen
- 1. C#: String.IndexOf zu FileStream.Seek
- 2. String.indexOf Funktion in C
- 3. Was ist mit diesem Funktionsaufruf falsch?
- 4. C# String.IndexOf() nicht richtig
- 5. String.IndexOf genaue Übereinstimmung
- 6. Was ist der Unterschied zwischen Funktionsaufruf und Funktionsreferenz?
- 7. Ist C++ Funktionsaufruf ein Ausdruck?
- 8. Java String.indexOf und leere Strings
- 9. Tabellenzugriff vs Funktionsaufruf + bedingte Bestimmung: Was ist schneller?
- 10. Was ist der Unterschied hinter normalen Funktionsaufruf und pcall
- 11. Was ist die Definition eines Implementierungsdetails?
- 12. Was ist die wahre Struktur eines Zeigers?
- 13. Was ist die praktische Grenze eines Textfelds?
- 14. Was ist die Definition eines Service-Objekts?
- 15. Was ist die maximale Speicherkapazität eines PLIST?
- 16. Was ist die Struktur eines Arrays?
- 17. Teilen eines Tupels in einem Funktionsaufruf
- 18. Extrahieren eines Funktionsaufrufnamens aus einem Funktionsaufruf
- 19. Was sind geschweifte Klammern nach Funktionsaufruf?
- 20. Angularjs das Ergebnis eines Funktionsaufruf beobachtet
- 21. Was ist die beste Vorgehensweise für die Durchführung eines Passwortvergleichs?
- 22. Was ist die Definition für die Höhe eines Baumes?
- 23. Was ist die Formel für die Berechnung eines Zeitstempels?
- 24. Ist die Funktionsdeklaration im Funktionsaufruf für ActionScript zulässig?
- 25. C++ virtueller Funktionsaufruf versus boost :: Funktionsaufruf speedwise
- 26. Kann Java String.indexOf() einen regulären Ausdruck als Parameter behandeln?
- 27. Ist das ein Fehler in Matlab Funktionsaufruf?
- 28. Wie mit meiner Funktionsaufruf Onclick Funktionsaufruf ersetzen
- 29. Was ist die zugrundeliegende Datenstruktur eines STL-Sets in C++?
- 30. Was ist attribute.spezifiziert für die Attribute eines DOM-Elements?
In welcher Sprache und im Vergleich zu was? Was sind die Argumente der Funktion - braucht es eine Zeichenfolge, ein Zeichen, einen benutzerdefinierten Vergleich? – Kobi
Ist es Java, von dem du sprichst? – NullUserException
duplicate of http://stackoverflow.com/questions/12752274/java-indexofstring-str-method-complexity –