Hola me gustaría saber cuál es la complejidad de tiempo de la función "replaceAll" de la clase String, pero no puedo encontrar ninguna información sobre él. (http://docs.oracle.com/javase/6/docs/api/java/lang/String.html)¿Por qué Java no incluye la complejidad de tiempo/espacio de cada función en el javadoc?
¿No sería mejor para Java para incluir las complejidades en el Javadoc? Creo que es algo muy importante que alguien sepa.
La mayoría de las funciones tienen complejidades de tiempo bastante sencillas. AFAIK, replaceAll es O (n)
En mi humilde opinión. No hay nada mejor que probar esto usted mismo empíricamente, p. con un generador de perfiles, porque es muy probable que el 99% de los métodos que utiliza tengan poco o ningún impacto en el rendimiento de su aplicación.
La complejidad puede documentarse si está garantizada. Por ejemplo, algunas de las clases de colecciones documentan garantías de complejidad. Por ejemplo, desde HashMap:
Esta aplicación proporciona un rendimiento constante en el tiempo de las operaciones básicas (get y put) ...
Sin embargo, a veces la complejidad es:
Los javadocs de la API de Java especifican un contrato general de lo que debe ser realizado por cada método, no cómo. Cada implementador de la API (por ejemplo, OpenJDK, JDK de Oracle, etc.) tiene cierta libertad sobre cómo implementar cada contrato, y esa libertad puede incluir hacer optimizaciones, incluso sacrificios en el rendimiento. Por lo tanto, los javadocs en general no especifican detalles como el tiempo/complejidad de las funciones, a menos que sea absolutamente necesario que un método cumpla ciertos requisitos de rendimiento.
Si está utilizando la complejidad espacio/tiempo de las operaciones básicas para tomar decisiones de diseño, es casi seguro que lo está haciendo mal.
Primero crea una aplicación correcta, luego perfilala. Luego optimice lo que el proceso de creación de perfiles revela como los cuellos de botella.
La respuesta general es que la complejidad generalmente depende de factores que son demasiado difíciles de analizar. Esto ciertamente se aplica para String.replaceAll, donde la complejidad efectiva depende críticamente de la cadena regex. (Una expresión regular mal diseñada puede hacer que la coincidencia sea lenta).