La complejidad del tiempo de la subcadena de Java ()

¿Cuál es la complejidad temporal del método String#substring() en Java?

Nueva respuesta

A partir de la actualización 6 dentro del ciclo de vida de Java 7, el comportamiento de la substring cambió para crear una copia, por lo que cada String refiere a un char[] que no se comparte con ningún otro objeto, hasta donde yo sé. Entonces, en ese punto, la substring() convirtió en una operación O (n) donde n es los números en la subcadena.

Respuesta anterior: pre-Java 7

No documentado, pero en la práctica O (1) si asume que no se requiere recolección de basura, etc.

Simplemente crea un nuevo objeto String que hace referencia al mismo char[] subyacente char[] pero con diferentes valores de desplazamiento y recuento. Entonces, el costo es el tiempo necesario para realizar la validación y construir un único objeto nuevo (razonablemente pequeño). Eso es O (1) en la medida en que es sensato hablar sobre la complejidad de las operaciones que pueden variar en el tiempo en base a la recolección de basura, cachés de CPU, etc. En particular, no depende directamente de la longitud de la cadena original o la subcadena .

Era O (1) en versiones anteriores de Java, como dijo Jon, acaba de crear un nuevo String con el mismo carácter subyacente [], y un desplazamiento y longitud diferentes.

Sin embargo, esto realmente ha cambiado comenzó con Java 7 actualización 6.

Se eliminó el uso compartido de char [] y se eliminaron los campos de desplazamiento y longitud. substring () ahora simplemente copia todos los caracteres en una nueva Cadena.

Ergo, subcadena es O (n) en Java 7 actualización 6

Ahora es complejidad lineal. Esto es después de solucionar un problema de pérdida de memoria para la subcadena.

Por lo tanto, desde Java 1.7.0_06 recuerde que String.substring ahora tiene una complejidad lineal en lugar de una constante.

O (1) porque no se realiza ninguna copia de la cadena original, solo crea un nuevo objeto envoltorio con información de compensación diferente.

Juzgue usted mismo por seguir, pero los inconvenientes de rendimiento de Java se encuentran en otra parte, no aquí en la subcadena de una cadena. Código:

 public static void main(String[] args) throws IOException { String longStr = "asjf97zcv.1jm2497z20`1829182oqiwure92874nvcxz,nvz.,xo" + "aihf[oiefjkas';./.,z][p\\°°°°°°°°?!(*#&(@*&#!)^(*&(*&)(*&" + "fasdznmcxzvvcxz,vc,mvczvcz,mvcz,mcvcxvc,mvcxcvcxvcxvcxvcx"; int[] indices = new int[32 * 1024]; int[] lengths = new int[indices.length]; Random r = new Random(); final int minLength = 6; for (int i = 0; i < indices.length; ++i) { indices[i] = r.nextInt(longStr.length() - minLength); lengths[i] = minLength + r.nextInt(longStr.length() - indices[i] - minLength); } long start = System.nanoTime(); int avoidOptimization = 0; for (int i = 0; i < indices.length; ++i) //avoidOptimization += lengths[i]; //tested - this was cheap avoidOptimization += longStr.substring(indices[i], indices[i] + lengths[i]).length(); long end = System.nanoTime(); System.out.println("substring " + indices.length + " times"); System.out.println("Sum of lengths of splits = " + avoidOptimization); System.out.println("Elapsed " + (end - start) / 1.0e6 + " ms"); } 

Salida:

  subcadena 32768 veces
 Suma de longitudes de divisiones = 1494414
 Transcurrido 2.446679 ms 

Si es O (1) o no, depende. Si solo hace referencia a la misma Cadena en la memoria, imagínese Cadena muy larga, haga una subcadena y deje de hacer referencia a la larga. ¿No sería bueno liberar memoria por uno largo?