necesito para calcular la complejidad del tiempo de la siguiente código:complejidad Tiempo de ciclo for anidado
for (i = 1; i <= n; i++)
{
for(j = 1; j <= i; j++)
{
// Some code
}
}
¿Es O (n^2)?
De hecho, es O (n^2). Vea también un ejemplo muy similar con el mismo tiempo de ejecución here.
Sí, los bucles anidados son una forma de obtener rápidamente una gran notación O.
Normalmente (pero no siempre) un bucle anidado en otro causará O (n²).
Piénselo, el ciclo interno se ejecuta i veces, para cada valor de i. El ciclo externo se ejecuta n veces.
por lo tanto se ve un patrón de ejecución de la siguiente manera: 1 + 2 + 3 + 4 + ... + n veces
Por lo tanto, podemos acotar el número de ejecuciones de código diciendo que, obviamente, se ejecuta más de n veces (límite inferior), pero en términos de n ¿cuántas veces estamos ejecutando el código?
Bueno, matemáticamente podemos decir que se ejecutará no más de n² veces, dándonos el peor de los casos y, por lo tanto, nuestro límite Big-Oh de O (n²). (Para obtener más información sobre cómo podemos decir matemáticamente este aspecto en el Power Series)
Big-Oh no siempre mide exactamente cuánto trabajo se está haciendo, pero generalmente ofrece una aproximación confiable del peor de los casos.
4 años más tarde Editar: Debido a este post parece conseguir una buena cantidad de tráfico. Quiero explicar más completamente cómo vinculamos la ejecución a O (n^2) usando la serie de potencia
Desde el sitio web: 1 + 2 + 3 + 4 ... + n = (n² + n)/2 = n²/2 + n/2. ¿Cómo, entonces estamos convirtiendo esto en O (n²)? Lo que (básicamente) estamos diciendo es que n²> = n²/2 + n/2. ¿Es esto cierto? Hagamos algo de álgebra simple.
Debe estar claro que n²> = n (no estrictamente mayor que, debido a que n = 0 o 1), suponiendo que n siempre es un número entero.
La complejidad real de Big O es ligeramente diferente de lo que acabo de decir, pero esta es la esencia de la misma. En realidad, la complejidad de Big O pregunta si hay una constante que podamos aplicar a una función de manera que sea más grande que la otra, para una entrada suficientemente grande (Consulte la página wikipedia)
¿Puedo hacer una pequeña pregunta aquí? ¿Qué pasa si la parte "// algún código" es algún cálculo con complejidad O (N)? ¿Cómo se calcula el resultado? Creo que este es el caso común en que una función llama a otra y considera que la última es una caja negra con cierta complejidad proporcionada por las especificaciones. –
@ShawnLe: observación perspicaz. En la mayoría de los supuestos, sí, suponemos que '// algún código' es O (1) y, por lo tanto, no se tiene en cuenta en la complejidad de Big O. Si de hecho fuera O (N), entonces nuestra complejidad total se vuelve O (N^3). Piense en ello como una multiplicación (porque lo es). Para ~ N iteraciones de bucle externo, el bucle interno itera ~ N veces, con cada iteración realizando ~ N trabajo. N veces N veces N = N^3. – AndyG
Primero consideraremos los bucles donde el número de las iteraciones del ciclo interno son independientes del valor del índice del ciclo externo.Por ejemplo:
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
sequence of statements
}
}
El ciclo externo se ejecuta N veces. Cada vez que se ejecuta el bucle externo, el bucle interno ejecuta M veces. Como resultado, las instrucciones en el ciclo interno ejecutan un total de N * M veces. Por lo tanto, la complejidad total para los dos bucles es O (N2).
Una forma rápida de explicar esto es visualizándolo.
si ambos i y j son de 0 a N, que es fácil de ver O (N^2)
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
en este caso, es:
O
O O
O O O
O O O O
O O O O O
O O O O O O
O O O O O O O
O O O O O O O O
Esto viene a ser 1/2 de N^2, que sigue siendo O (N^2)
Gracias por ayudarme finalmente a comprender cómo los bucles internos con una condición j <= i resultan en 1/2 N^2. Esto me ha estado molestando por algun tiempo. ¿Puedes explicar cómo sigue siendo O (N^2)? –
Debido a la ley de Moore, podemos suponer que la velocidad de ejecución del algoritmo se duplica cada 18 meses. Debido a esto, al analizar los algoritmos, podemos soltar el coeficiente y solo enfocarnos en los algoritmos en términos de n. Básicamente, O (n^2) tomará O (1/2 n^2) en 18 meses. Sin embargo, como n crece más alto, el tiempo de ejecución crece exponencialmente, mientras que para un algoritmo de tiempo lineal, crece con n. –
Entonces, ¿qué dices es que al calcular la notación grande de Oh, el 1/2 en 1/2 (n^2) no es importante, debido en parte al hecho de que los coeficientes se vuelven irrelevantes en el tiempo? La parte importante de ese término -de nuevo, en términos de gran Oh- es que es cuadrático, ¿no que es un cuadrático que se reduce a la mitad? –
En la 1ra iteración del bucle externo (i = 1), el bucle interno iterará 1 veces En la 2da iteración del exterior lazo (i = 2), el interior loop repetirá 2 veces En la 3ra iteración del bucle externo (i = 3), el bucle interno iterará 3 veces
.
.
En la iteración final del bucle exterior (i = n), el bucle interior se iterate n veces
Así, el número total de veces que los estados en el bucle interior se ejecutarán será igual a la suma de los números enteros de 1 a n, que es:
((n)*n)/2 = (n^2)/2 = O(n^2) times
duplicados de http://stackoverflow.com/questions/362059/big-o-of-this-nested-loop –
Mi pregunta no es exactamente un duplicado del que enlazó, pero es una pregunta común, así que supongo que se formula de muchas formas. – yyy
Relacionado: [Cómo encontrar la complejidad temporal de un algoritmo] (https://stackoverflow.com/q/11032015) – Dukeling