Tiempo de ejecucion

[nolasco281]

Hola como estan.

Tengo una duda con respecto al tiempo de ejecucion de acuardo a instrucciones.

Tal vez alquien me pueda explicar por que esto es asi.

Por ejemplo:



Vi esto pero no exiplica por que es asi o por que en el segundo bucle cambia hablando algebraicamente.

Recuardo haber visto sumatorias pero, para encontrar areas en integrales.



entiendo que:

Código (cpp) [Seleccionar] Expandir

for (int i = 0; i < n; i++) //El tiempo de este bucle seria de O(n)

[eferion]

Las sumatorias te permiten calcular el número de veces que se va a ejecutar el bucle... no el tiempo de ejecución.

Código (c) [Seleccionar] Expandir

for( i=1; i<n; i++ )
Este bucle se ejecuta n veces.

Código (c) [Seleccionar] Expandir

for( j=i+1, j<=n; j++ )
Este bucle se va a ejecutar desde i+1 hasta n... n veces, teniendo en cuenta que i va a ir variando en cada una de esas n veces. Es decir, se va a ejecutar n+(n-1)+(n-2)+(n-3)+...+1. Para expresar esta ecuación de forma genérica necesitas un sumatorio.

Código (c) [Seleccionar] Expandir

for( k=1; k<=j; k++ )
El número de veces que se ejecuta este bucle depende de j, por lo que también depende de i. En este caso necesitas un sumatorio doble porque dependes de dos variables que van variando en cada iteración.

[nolasco281]

Hola gracias 

Entendi muy bien la explicacion te lo agardesco esta un poco con fundido en cuanto a como trabajaba

una ultima pregunta segundo, el tiempo de ejecucion de estos bucles seria O(n^3) no?

segun lo que entendi.

Gracias y saludos de nuevo.

[eferion]

El tiempo de ejecución de un bucle anidado es algo más complicado porque tienes que tener en cuenta el número total de repeticiones del bucle... Ahí es donde entra en juego las ecuaciones de los sumatorios.

Por ejemplo. El tiempo de ejecución de una iteración del primer bucle será igual O(numero de veces que se ejecuta el código del tercer bucle * numero de instrucciones en el tercer bucle )

[nolasco281]

Muchisimas gracias cosas que no explican los libros y si lo hace, lo hacen de forma muy confusa
Ya entendi y me quedo claro las explicaciones. ahora a practicar y sequir leyendo.

Gracias de nuevo y saludos.