Analizando algoritmos para la complejidad del tiempo

Question

Estoy analizando un algoritmo y solo quiero saber si estoy en el camino correcto.

Para este algoritmo, solo estoy contando las multiplicaciones en la línea que tienen *** en ellas.

Aquí está el algoritmo:

1. Así que estoy empezando desde la línea interior más, puedo ver que hay 2 operaciones allí (las dos multiplicaciones).
2. Ahora estoy mirando los 2 bucles más internos, por lo que puedo decir que el p=p*20*z se ejecuta exactamente (j) + (j-1)+(j-2)+(j-3)...1 veces. Esto pasa a ser igual a j(j+1)/2.
3. Entonces en total, ya que hay dos multiplicaciones, sucede 2 * (j(j+1)/2).
4. Entonces, finalmente, el bucle "i" ocurre exactamente n veces, por lo que, en total, es n(2 * (n(n+1)/2)).

Ese es mi proceso de pensamiento detrás de esto. ¿Estoy en lo correcto? Gracias.

Answer 1

Su proceso de pensamiento es correcto. Necesita reemplazar el término j con una n (n es el mayor valor que j puede asumir), pero probablemente sea un error tipográfico.

Por otra parte, se puede simplificar aún más desde donde estás:

n(2*(n(n+1)/2)) 
2*n*(n^2+n)/2 
n^3+n^2 

=> O(n^3) 

El último paso es debido a que el término n en cubos crecerá a un ritmo mucho mayor que el n al cuadrado plazo podemos decir que dominará el tiempo de ejecución para n grande. Solo otro punto que mencionaría es que quizás debas considerar la tienda p como una operación así como las dos multiplicaciones, aunque obviamente esto no cambiará el tiempo de ejecución simplificado de big-o.

Answer 2

Computación en este ejemplo particular podría simplificarse si se puede descubrir que los tres bucles tiene la misma condición de salida up to n:

1. i <= n
2. j <= n
3. k <= j

Básicamente tercer ciclo correría n iteraciones también porque j <= n por lo k <= n, esto quiere decir que la complejidad sería n * n * n = O(n^3)

Answer 3

Esto es cómo se puede obtener el orden de crecimiento de su algoritmo de forma metódica: