Haz todo lo posible por comprender el código bien previamente a usarlo a tu trabajo si ttienes algo que aportar puedes compartirlo con nosotros.
Solución:
Sí, los bucles anidados son una forma de obtener rápidamente una notación O grande.
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 bucle exterior se ejecuta n veces.
entonces ves un patrón de ejecución como este: 1 + 2 + 3 + 4 + … + n veces
Por lo tanto, podemos limitar 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 no se ejecutará 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 esto, mire la serie Power)
Big-Oh no siempre mide exactamente cuánto trabajo se está realizando, pero generalmente brinda una aproximación confiable del peor de los casos.
4 años después Editar: Porque esta publicación parece tener una buena cantidad de tráfico. Quiero explicar con más detalle cómo vinculamos la ejecución a O(n²) usando la serie de potencias
Del sitio web: 1+2+3+4…+n = (n² + n)/2 = n²/2 + n/2. Entonces, ¿cómo estamos convirtiendo esto en O(n²)? Lo que (básicamente) estamos diciendo es que n² >= n²/2 + n/2. Es esto true? Hagamos algo de álgebra simple.
- Multiplica ambos lados por 2 para obtener: 2n² >= n² + n?
- Expande 2n² para obtener: n² + n² >= n² + n?
- Resta n² de ambos lados para obtener: n² >= n?
Debe quedar claro que n² >= n (no estrictamente mayor que, por el caso donde n=0 o 1), asumiendo que n es siempre un número entero.
La complejidad real de Big O es ligeramente diferente de lo que acabo de decir, pero esta es la esencia. En realidad, la complejidad de Big O pregunta si hay una constante que podamos aplicar a una función de modo que sea más grande que la otra, para una entrada lo suficientemente grande (consulte la página de wikipedia)
Una forma rápida de explicar esto es visualizarlo.
si tanto i como j son de 0 a N, es fácil 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 resulta ser la mitad de N ^ 2, que sigue siendo O (N ^ 2)
De hecho, es O (n ^ 2). Vea también un ejemplo muy similar con el mismo tiempo de ejecución aquí.
Recuerda algo, que puedes permitirte parafrasear si te fue útil.