Herramientas de usuario
algoritmos-oia:analisis-amortizado
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa | |||
|
algoritmos-oia:analisis-amortizado [2017/11/23 22:00] santo |
algoritmos-oia:analisis-amortizado [2017/11/23 22:02] (actual) santo |
||
|---|---|---|---|
| Línea 33: | Línea 33: | ||
| - Las operaciones de tipo 1 son $O(1)$, y por lo tanto en total ejecutarlas todas tiene un costo $O(N)$ | - Las operaciones de tipo 1 son $O(1)$, y por lo tanto en total ejecutarlas todas tiene un costo $O(N)$ | ||
| - | - Las operaciones de tipo 2 son en total $O(N)$, y lo único "caro" que hacen es borrar elementos, pero **en total**, el costo total de los borrados es $O(N)$. Por lo tanto el costo total de hacer **todas** las operaciones de este tipo será también $O(N)$. | + | - Las operaciones de tipo 2 son en total $O(N)$, y lo único "caro" que hacen es borrar elementos, pero **en total**, el costo de los borrados es $O(N)$. Por lo tanto el costo total de hacer **todas** las operaciones de este tipo será también $O(N)$. |
| - El costo total de ejecutar todas las operaciones es, por los dos anteriores, $O(N)$. | - El costo total de ejecutar todas las operaciones es, por los dos anteriores, $O(N)$. | ||
| - Entonces, como $N$ operaciones siempre tienen un costo proporcional a $N$, el **costo promedio por operación** resulta ser $\frac{N}{N} = 1$. Decimos entonces que ambas operaciones tienen un costo $O(1)$ **amortizado**: podemos pensar que ambas cuestan $O(1)$, y el costo final que obtendremos al calcular será el correcto. | - Entonces, como $N$ operaciones siempre tienen un costo proporcional a $N$, el **costo promedio por operación** resulta ser $\frac{N}{N} = 1$. Decimos entonces que ambas operaciones tienen un costo $O(1)$ **amortizado**: podemos pensar que ambas cuestan $O(1)$, y el costo final que obtendremos al calcular será el correcto. | ||
algoritmos-oia/analisis-amortizado.1511474456.txt.gz · Última modificación: 2017/11/23 22:00 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
