paneles - table swing java

¿Cuál es la complejidad de esta simple pieza de código? (10)

Aquí está mi cálculo de cómo obtuvieron O (n ^ 2)

Ignoraremos el tiempo de CPU para declarar el StringBuffer, ya que no varía con el tamaño de la cadena final.

Cuando calculamos la complejidad O, nos preocupamos por el peor de los casos, esto ocurrirá cuando hay cadenas de 1 letra. Explicaré después de este ejemplo:

Digamos que tenemos 4 cadenas de una letra: ''A'', ''B'', ''C'', ''D''.

Lea en A: tiempo de CPU para encontrar el final de StringBuffer: 0 tiempo de CPU para agregar ''A'': 1

Lea en B: tiempo de CPU para encontrar el final de StringBuffer: 1 tiempo de CPU para agregar ''B'': 1

Lea en C: tiempo de CPU para encontrar el final de StringBuffer: 2 tiempo de CPU para agregar ''C'': 1

Lea en D: tiempo de CPU para encontrar el final de StringBuffer: 3 tiempo de CPU para agregar ''D'': 1

Tiempo de CPU para copiar StringBuffer a String al final: 4

Tiempo total de CPU = 1 + 2 + 3 + 4 + 4

Si generalizamos esto a n palabras de 1 letra:

1 + 2 + 3 + ...... + n + n = 0.5n (n + 1) + n

Hice esto usando la fórmula para la suma de una secuencia aritmética.

O (0.5n ^ 2 + 1.5n) = O (n ^ 2).

Si usamos palabras de varias letras, tendremos que encontrar el final del StringBuffer con menos frecuencia, lo que llevará a un menor tiempo de CPU y un caso "mejor".

Estoy pegando este texto de un libro electrónico que tengo. Dice la complejidad si O (n ² ) y también da una explicación para ello, pero no veo cómo.

Pregunta: ¿Cuál es el tiempo de ejecución de este código?

public String makeSentence(String[] words) { StringBuffer sentence = new StringBuffer(); for (String w : words) sentence.append(w); return sentence.toString(); }

La respuesta que dio el libro:

O (n ² ), donde n es el número de letras en la oración. He aquí por qué: cada vez que agregas una cadena a una oración, creas una copia de la oración y repasas todas las letras de la oración para copiarlas. Si tienes que iterar hasta n caracteres cada vez en el ciclo, y estás haciendo un bucle al menos n veces, eso le da un tiempo de ejecución O (n ² ). ¡Ay!

¿Puede alguien explicar esta respuesta con más claridad?

Como la explicación dada en el libro, para cada palabra en la matriz de cadenas se crea un nuevo objeto de oración y esa oración primero copia la oración anterior y luego atraviesa el final de la matriz y luego agrega la nueva palabra, de ahí la complejidad de n^2 .

Primero ''n'' para copiar la oración anterior en un nuevo objeto
Segundo ''n'' para atravesar esa matriz y luego agregarla

Por lo tanto, n*n será n^2 .

Creo que este texto en el libro debe ser un error tipográfico, creo que el contenido correcto está abajo, lo arreglé:

================================================== =================

Pregunta: ¿Cuál es el tiempo de ejecución de este código?

public String makeSentence(String[] words) { String sentence = new String(""); for (String w : words) sentence+=W; return sentence; }

Respuesta: O (n ² ), donde n es el número de letras en la oración. He aquí por qué: cada vez que agregas una cadena a una oración, creas una copia de la oración y repasas todas las letras de la oración para copiarlas. Si tiene que recorrer hasta n caracteres cada vez en el bucle, y está haciendo un ciclo al menos n veces, eso le da un tiempo de ejecución O (n ² ). ¡Ay! Con StringBuffer (o StringBuilder) puede ayudarte a evitar este problema.

public String makeSentence(String[] words) { StringBuffer sentence = new StringBuffer(); for (String w : words) sentence.append(w); return sentence.toString(); }

================================================== ===================

Estoy en lo cierto?

Es un poco difícil responder a una pregunta sobre la complejidad de este código cuando se escribe a un nivel alto, lo que aleja los detalles de la implementación. La documentación de Java no parece ofrecer ninguna garantía en términos de la complejidad de la función de append . Como otros han señalado, la clase StringBuffer puede (y debe) escribirse de modo que la complejidad de las cadenas anexas no dependa de la longitud actual de la cadena contenida en StringBuffer .

Sin embargo, sospecho que no es tan útil para la persona que hace esta pregunta decir simplemente "¡su libro está equivocado!" - en cambio, veamos qué suposiciones se están haciendo y aclaremos lo que el autor estaba tratando de decir.

Puede hacer las siguientes suposiciones:

Crear un new StringBuffer es O (1)
Obtener la siguiente cadena w en words es O (1)
sentence.toString retorno. La sentence.toString es a lo sumo O (n).

La pregunta es en realidad cuál es el orden de la sentence.append(w) , y eso depende de cómo suceda dentro del StringBuffer . La manera ingenua es hacerlo como Shlemiel el pintor .

La forma tonta

Supongamos que utiliza una cadena terminada en nulo de estilo C para el contenido de StringBuffer . La forma en que encuentra el final de dicha cadena es leyendo cada uno de los caracteres, uno por uno, hasta que encuentre el carácter nulo. Luego, para agregar una nueva cadena S, puede comenzar a copiar caracteres de S a la cadena StringBuffer (terminando con otra carácter nulo). Si escribe append esta manera, es O ( a + b ), donde a es el número de caracteres actualmente en el StringBuffer , y b es el número de caracteres en la nueva palabra. Si recorre una serie de palabras y cada vez que tiene que leer todos los caracteres que acaba de agregar antes de agregar la nueva palabra, entonces la complejidad del bucle es O (n ^ 2), donde n es el número total de caracteres en todas las palabras (también el número de caracteres en la oración final).

Una mejor manera

Por otro lado, supongamos que el contenido de StringBuffer sigue siendo una matriz de caracteres, pero también almacenamos un size entero que nos dice qué tan larga es la cadena (número de caracteres). Ahora ya no tenemos que leer todos los caracteres en el StringBuffer para encontrar el final de la cadena; solo podemos buscar el size índice en la matriz, que es O (1) en lugar de O ( a ). Entonces, la función de append ahora solo depende de la cantidad de caracteres que se agregan, O ( b ). En este caso, la complejidad del bucle es O (n), donde n es el número total de caracteres en todas las palabras.

... ¡No hemos terminado todavía!

Finalmente, hay un aspecto más de la implementación que aún no se ha cubierto, y ese es el que realmente se menciona en la respuesta del libro de texto: asignación de memoria. Cada vez que desee escribir más caracteres en su StringBuffer , no se garantiza que tenga suficiente espacio en la matriz de caracteres para que se ajuste a la nueva palabra. Si no hay suficiente espacio, su computadora necesita primero asignar un poco más de espacio. en una sección limpia de la memoria, y luego copie toda la información en la antigua matriz StringBuffer través, y luego puede continuar como antes. Copiar datos como este tomará O ( a ) tiempo (donde a es el número de caracteres que se copiarán).

En el peor de los casos, debe asignar más memoria cada vez que agregue una nueva palabra. Básicamente, esto nos lleva de nuevo al cuadrado donde el bucle tiene una complejidad O (n ^ 2), y es lo que parece sugerir el libro. Si asume que no ocurre nada loco (¡las palabras no se alargan a un ritmo exponencial !), Entonces probablemente pueda reducir el número de asignaciones de memoria a algo más parecido a O (log (n)) haciendo que la memoria asignada crezca exponencialmente Si ese es el número de asignaciones de memoria, y las asignaciones de memoria en general son O ( a ), entonces la complejidad total atribuida solo a la administración de memoria en el bucle es O (n log (n)). Dado que el trabajo agregado es O (n) y menor que la complejidad de la administración de la memoria, la complejidad total de la función es O (n log (n)).

Nuevamente, la documentación de Java no nos ayuda en términos de cómo crece la capacidad de StringBuffer , simplemente dice "Si el búfer interno se desborda, se hace automáticamente más grande". Dependiendo de cómo suceda, podría terminar con O (n ^ 2) o O (n log (n)) en general.

Como ejercicio que le queda al lector: Encuentre una manera fácil de modificar la función para que la complejidad general sea O (n), eliminando los problemas de reasignación de memoria.

Eso realmente depende de la implementación de StringBuffer . Suponiendo que .append() era tiempo constante, está claro que tiene un algoritmo O(n) en el tiempo donde n = length of the words array . Si .append no es un tiempo constante, deberá multiplicar su O (n) por la complejidad del método. Si de hecho la implementación actual de StringBuffer copia cadenas por caracteres, entonces el algoritmo anterior es

Θ(n*m) , o O(n*m) , donde n es el número de palabras y m es la longitud de palabra promedio, y su libro es incorrecto. Supongo que estás buscando un límite estricto.

Ejemplo simple de que la respuesta del libro es incorrecta: String[] words = [''alphabet''] Según la definición del libro, n=8 , por lo que el algoritmo estará limitado por 64 pasos. ¿Es este el caso? Claramente no estrictamente. Veo 1 operación de asignación y 1 de copia con n caracteres, así que obtienes unos 9 pasos. Este tipo de comportamiento es predicho por los límites de O(n*m) , como ilustré anteriormente.

Hice algunas excavaciones, y esto claramente no es una copia de un personaje simple. Parece que la memoria se está copiando a granel, lo que nos pone de nuevo en O(n) , su primera suposición sobre la solución.

/* StringBuffer is just a proxy */ public AbstractStringBuilder append(String str) { if (str == null) str = "null"; int len = str.length(); ensureCapacityInternal(count + len); str.getChars(0, len, value, count); count += len; return this; } /* java.lang.String */ void getChars(char dst[], int dstBegin) { System.arraycopy(value, offset, dst, dstBegin, count); }

Tu libro es viejo, terrible, o ambos. No estoy lo suficientemente determinado como para revisar las versiones de JDK para encontrar una implementación menos óptima de StringBuffer, pero tal vez exista una.

Esto parece ser una cuestión de error, porque acabo de leer ese libro justo ahora. Esta parte del texto en el libro es un error tipográfico! Aquí está el contexto:

================================================== =================

Pregunta: ¿Cuál es el tiempo de ejecución de este código?

1 public String makeSentence(String[] words) { 2 StringBuffer sentence = new StringBuffer(); 3 for (String w : words) sentence.append(w); 4 return sentence.toString(); 5 }

================================================== ===================

¿Te has dado cuenta de que el autor lo arruinó? La solución de O (n ² ) que mencionó (la primera) era exactamente la misma que la "optimizada" (la última). Por lo tanto, mi conclusión es que el autor intentaba representar otra cosa, como copiar siempre la oración anterior en un búfer nuevo al agregar cada cadena siguiente, como el ejemplo de un algoritmo O (n ² ). StringBuffer no debería ser tan tonto, ya que el autor también mencionó que "Con StringBuffer (o StringBuilder) puede ayudarlo a evitar este problema".

Hay un error tipográfico en este libro.

1er caso :

public String makeSentence(String[] words) { String sentence = new String(); for (String w : words) sentence += w; return sentence; }

Complejidad: O (n ^ 2) -> (n palabras) x (n caracteres copiados en cada iteración, para copiar la oración actual en un StringBuffer)

2º caso :

public String makeSentence(String[] words) { StringBuffer sentence = new StringBuffer(); for (String w : words) sentence.append(w); return sentence.toString(); }

Complejidad: O (n) -> (n palabras) x O (1) (complejidad amortizada para la concatenación de StringBuffer)

Intenté comprobarlo utilizando este programa.

public class Test { private static String[] create(int n) { String[] res = new String[n]; for (int i = 0; i < n; i++) { res[i] = "abcdefghijklmnopqrst"; } return res; } private static String makeSentence(String[] words) { StringBuffer sentence = new StringBuffer(); for (String w : words) sentence.append(w); return sentence.toString(); } public static void main(String[] args) { String[] ar = create(Integer.parseInt(args[0])); long begin = System.currentTimeMillis(); String res = makeSentence(ar); System.out.println(System.currentTimeMillis() - begin); } }

Y el resultado fue, como se esperaba, O (n):

Prueba de java 200000 - 128 ms

Prueba de java 500000 - 370 ms

Prueba de java 1000000 - 698 ms

Versión 1.6.0.21

La respuesta aceptada es simplemente incorrecta. StringBuffer ha amortizado el apéndice O (1), por lo que n los apéndices serán O ( n ).

Si no fuera el apéndice O (1), StringBuffer no tendría ninguna razón para existir, ya que escribir ese bucle con concatenación de String simple también sería O ( n ^ 2).

Me parece O (n) para mí (siendo n el número total de letras en todas las palabras). Básicamente estás iterando sobre cada carácter en words para agregarlo en el StringBuffer .

La única forma en que puedo ver esto como O (n ^ 2) es si append() itera todos los contenidos en el búfer antes de agregar cualquier carácter nuevo. Y puede hacerlo de vez en cuando si el número de caracteres excede la longitud del búfer asignado actualmente (tiene que asignar un búfer nuevo y luego copiar todo desde el búfer actual al búfer nuevo). Pero no ocurrirá en todas las iteraciones, por lo que aún no tendrá O (n ^ 2).

Como máximo, tendría O (m * n), donde m es el número de veces que aumenta la longitud del búfer. Y como StringBuffer duplicará el tamaño de su búfer cada vez que asigne un búfer más grande, podemos determinar que m es aproximadamente igual a log2(n) (en realidad log2(n) - log2(16) , ya que el tamaño del búfer inicial predeterminado es 16 en su lugar de 1).

Entonces, la respuesta real es que el ejemplo del libro es O (n log n), y que puede reducirlo a O (n) preasignando un StringBuffer con una capacidad lo suficientemente grande como para contener todas sus letras.

Tenga en cuenta que en Java, al agregar una cadena usando += , se muestra el comportamiento ineficiente descrito en la explicación del libro, ya que tiene que asignar una nueva cadena y copiar en ella todos los datos de ambas cadenas. Así que si haces esto, es O (n ^ 2):

String sentence = ""; for (String w : words) { sentence += w; }

Pero el uso de StringBuffer no debe generar el mismo comportamiento que en el ejemplo anterior. Esa es una de las razones principales por las que StringBuffer existe en primer lugar.