9
¿Cuál es el coste/complejidad de un String.indexOf() llamada a la función¿Cuál es el coste/complejidad de una llamada de función String.indexOf()
A
Respuesta
0
en Java, si la llamada es string1.indexOf (cadena2) el costo de tiempo sería O (m - n) donde m es la longitud de string1 yn es la longitud de string2. implementación de .indexOf() de
9
IIRC Java es sólo el naive string matching algorithm, que es la media y O(n+m)O(n*m) peor de los casos.
En la práctica esto es lo suficientemente rápido; Lo probé para cadenas relativamente grandes de aguja (> 500 caracteres) y pajar (pocos MB) y haría la coincidencia en menos de un segundo (en una computadora doméstica promedio). Eso sí, lo obligué a recorrer todo el pajar.
+0
Sé que hace mucho tiempo, pero ¿sabes de dónde sacaste eso? Necesitaría esa información para mi tesis de licenciatura y no sé si Stackoverflow sería una referencia aceptable para una tesis;) – odaa
+0
@odaa Realicé algunos experimentos y escribí un artículo cuando estaba en la universidad. – NullUserException
+0
@NullUserException, ¿Por qué dices que 'O (n + m)' es el caso promedio? http://stackoverflow.com/a/12752295/632951 parece contradecir ese punto. – Pacerier
0
Depende de la implementación.
Por ejemplo, al buscar una cadena dentro de una cadena más larga, "El algoritmo Turbo Boyer-Moore toma una cantidad constante adicional de espacio para completar una búsqueda dentro de 2n comparaciones (en oposición a 3n para Boyer-Moore), donde n es el número de caracteres en el texto que se buscará ". (ver Wikipedia).
+1
@caleb: De verdad, ¿cómo puedes saber por la pregunta? –
Cuestiones relacionadas
- 1. ¿Cuál es el significado de "()" en una llamada a función?
- 2. Función String.indexOf en C
- 3. ¿Cuál es la ventaja de esta llamada de función indirecta?
- 4. ¿Cuál es la desventaja de utilizar el preprocesador para definir una llamada a función?
- 5. string.IndexOf performance
- 6. @ personaje antes de una llamada de función
- 7. ¿Cuál es la duración de una llamada de Ajax?
- 8. ¿Cuál es el __proto__ de la función?
- 9. ¿Cuál es el alcance de una función en Javascript/ECMAScript?
- 10. ¿Cuál es el sentido de una función virtual pura privada?
- 11. ¿Cuál es la mejor manera de enviar QStrings en una llamada a función?
- 12. ¿Cómo arreglo una llamada de función "ambigua"?
- 13. ¿Cuál es la semántica de una función miembro miembro?
- 14. ¿Cuál es el orden predeterminado de una lista devuelta por una llamada de filtro de Django?
- 15. Rendimiento de String.indexOf OrdinalIgnoreCase vs CurrentCultureIgnoreCase
- 16. cómo devolución de llamada una función lua de función ac
- 17. Función de llamada jQuery desde una cadena
- 18. extrayendo un nombre de llamada de función de una llamada a función
- 19. función de Llamada basado en una cadena
- 20. Anular una llamada de función en C
- 21. SetTimeout no retrasa una llamada de función
- 22. ¿Cuál es el punto de la función de prototipos?
- 23. ¿Función de llamada de DLL?
- 24. función de devolución de llamada que significa
- 25. ¿Cuál es el tiempo de vida de una variable estática en una función de C++?
- 26. Java String.indexOf y cadenas vacías
- 27. ¿cuál es el uso de indicadores de función?
- 28. Cómo ejecutar una función dentro de una llamada de eco
- 29. ¿Cuál es la ventaja de usar una llamada a generic-where-clause sobre una llamada no genérica?
- 30. ¿Cuál es la sintaxis de una función estática?
¿En qué idioma, y en comparación con qué? ¿Cuáles son los argumentos de la función? ¿Se necesita una cadena, un char, un comparador personalizado? – Kobi
¿Es de Java de lo que estás hablando? – NullUserException
duplicado de http://stackoverflow.com/questions/12752274/java-indexofstring-str-method-complexity –