9
Qual è il costo/complessità di uno String.IndexOf() chiamata di funzioneQual è il costo/complessità di una chiamata di funzione String.IndexOf()
A
risposta
0
In Java, se la chiamata è string1.indexOf (string2) il costo del tempo sarebbe O (m - n) dove m è la lunghezza di string1 e n è la lunghezza di stringa2. implementazione di
9
IIRC Java di .indexOf() è solo l'naive string matching algorithm, che è O(n+m) media e O(n*m) caso peggiore.
In pratica questo è abbastanza veloce; L'ho provato per gli spilli relativamente grandi (> 500 char) e haystack (pochi MB) e farebbe la corrispondenza in meno di un secondo (in un normale computer domestico). Intendiamoci, l'ho costretto a passare attraverso l'intero pagliaio.
+0
So che è molto tempo fa ma sai da dove lo hai preso? Avrei bisogno di queste informazioni per la mia tesi di laurea e non so se Stackoverflow sarebbe un riferimento accettabile per una tesi;) – odaa
+0
@odaa Ho fatto alcuni esperimenti e ho scritto un articolo su di esso quando ero al college. – NullUserException
+0
@NullUserException, perché dici che 'O (n + m)' è il caso medio? http://stackoverflow.com/a/12752295/632951 sembra contraddire questo punto. – Pacerier
0
A seconda dell'implementazione. Ad esempio, quando si cerca una stringa all'interno di una stringa più lunga, "L'algoritmo di Turbo Boyer-Moore richiede una quantità aggiuntiva di spazio per completare una ricerca all'interno di confronti 2n (a differenza di 3n per Boyer-Moore), dove n è il numero di caratteri nel testo da cercare. " (vedi Wikipedia).
+1
@ caleb: Davvero, come puoi dire dalla domanda? –
Problemi correlati
- 1. Qual è il significato di "()" in una chiamata di funzione?
- 2. Funzione string.indexOf in C
- 3. Qual è il vantaggio di questa chiamata di funzione indiretta?
- 4. Qual è il modo migliore per inviare QStrings in una chiamata di funzione?
- 5. Qual è la differenza tra una chiamata di funzione e un riferimento alla funzione?
- 6. La chiamata della funzione Dll è più veloce di una normale chiamata di funzione?
- 7. Qual è la convenzione di chiamata predefinita di una funzione lambda C++?
- 8. python - chiamata da parte di una funzione
- 9. Qual è il tipo di una funzione lambda?
- 10. Qual è il punto di una funzione privata pura virtuale?
- 11. Chiamata di una funzione prima di Load
- 12. Qual è il significato di questa definizione di funzione?
- 13. Qual è il limite di chiamata dell'API grafico di Facebook?
- 14. estraendo una chiamata nome funzione da una funzione chiamata
- 15. Angular.js guardare il risultato di una chiamata di funzione
- 16. Qual è lo svantaggio dell'uso del preprocessore per definire una chiamata di funzione?
- 17. prestazioni di String.IndexOf OrdinalIgnoreCase vs CurrentCultureIgnoreCase
- 18. La chiamata di funzione sovraccaricata è ambigua
- 19. Ignora una chiamata di funzione in C
- 20. chiamata di una funzione utilizzando namespace
- 21. SetTimeout non ritardare una chiamata di funzione
- 22. Perché il mio string.indexof (char) è più veloce?
- 23. Perché il metodo String.indexOf non è parte dell'interfaccia CharSequence?
- 24. C# string.IndexOf() restituisce il valore imprevisto
- 25. Qt 4.5 - Il segnale di emissione è una chiamata di funzione o un thread e blocca?
- 26. Come contare il numero di volte in cui è stata chiamata una funzione, il modo FP
- 27. Qual è il significato di una funzione senza un argomento 'self' all'interno di una classe?
- 28. Qual è il tipo di ritorno per una funzione che restituisce un'altra funzione
- 29. Qual è l'equivalente Java di C# "Contesto logico di chiamata"
- 30. Qual è la sintassi di una funzione statica?
In quale lingua e rispetto a cosa? Quali sono gli argomenti della funzione: prende una stringa, un carattere, un confronto personalizzato? – Kobi
E 'java di cui stai parlando? – NullUserException
duplicato di http://stackoverflow.com/questions/12752274/java-indexofstring-str-method-complexity –