Recientemente comencé con esto, así que necesito su ayuda. Digamos que ha anidado los bucles for como se muestra a continuación, ambos van de 1 a n, ¿cómo se calcula el tiempo de ejecución para el mismo en términos de Big O, Theta, Omega?
for(i=1; i<n; i++) {
for(j=1; j<n; j++) {
//some piece of code
}
}
¡Gracias de antemano!
for(i=1; i<n; i++) {
for(j=1; j<n; j++) {
//some piece of code
}
}
Así que echemos un vistazo más de cerca a este código. Digamos que tenemos un conjunto de 10 elementos (n) y ejecutamos estos bucles uno por uno. Primero tiene que pasar el bucle i. lo pasa por 1, luego ese 1 entra en el segundo bucle 10 veces antes de que 1 se convierta en 2. En total tiene que pasar el bucle 100 veces antes de llegar al final. En notación O grande, siempre calculamos O para el peor de los casos. Es decir, necesita un elemento que se encuentra al final de su ciclo. Digamos que sumamos 1 an. ¿Cuántas veces tiene que pasar el bucle ahora? 11 * 11 y eso es 121. Entonces, siempre que su entrada crece 1, el costo de este algoritmo crece exponencialmente. Por eso decimos O (n ^ 2).
¡Espero que tenga sentido para ti!
Este artículo se recopila de Internet, indique la fuente cuando se vuelva a imprimir.
En caso de infracción, por favor [email protected] Eliminar
Déjame decir algunas palabras