Hola. Estaba leyendo del análisis amortizado pero hay algo que no me quedó del todo claro.
¿Tardan lo mismo un for con dos operaciones en cada repeticion que dos for con una operacion? (ambos for tienen la misma cantidad de repeticiones).
Muchas gracias
Voy a asumir que estabas leyendo de la wiki
En general se dice que uno hace un análisis amortizado de los pasos que realiza un algoritmo cuando uno acota la cantidad de pasos que hace un algoritmo globalmente a pesar de que quizá en algún paso del algortimo se realizaron muchos pasos
En general, un “for con dos operaciones en cada repetición” va a hacer un total de 2n operaciones, con n la cantidad de repeticiones. Entiendo que sería algo así:
for de 1 a n:
operación 1
operación 2
Después, al hablar de “dos for con una operación” no sé bien si te referís a algo del estilo:
for de 1 a n:
operación 1
for de 1 a n:
operación 2
En este caso también se realizan 2n operaciones, n por cada for.
O a esto otro:
for de 1 a n:
for de 1 a n:
operación 1
En este caso se realizan n^2 operaciones, pues por cada iteración del primer for, se hacen n iteraciones del segundo en las cuales se realiza la operación.
En ninguno de los casos que estoy entendiendo diría que se puede hacer un análisis amortizado de la cantidad de operaciones.
Si con los ejemplos de la wiki no quedó claro, agrego este otro que se encuentra en la charla de Ventanas Deslizantes del Nacional pasado que podés descargar en este post Charlas Nacional 2017. De ese .pdf salteate la parte de búsqueda binaria y leé los primeros ejemplos de Ventana Deslizante.
2 Me gusta