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 Próxima revisión | 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 20: | Línea 20: | ||
| Tanto los $x$ como los $k$ de las operaciones anteriores son arbitrarios, y por ejemplo podemos pensar que los elige un usuario, o se leen de la entrada, sin que tengamos control sobre ellos. | Tanto los $x$ como los $k$ de las operaciones anteriores son arbitrarios, y por ejemplo podemos pensar que los elige un usuario, o se leen de la entrada, sin que tengamos control sobre ellos. | ||
| - | La pregunta que nos hacemos es, ¿Cuál es la complejidad de estas dos operaciones? La operación 1, de agregar, es la más simple, pues consistirá de un único ''.push()'' en el stack, que ya sabemos que tiene complejidad $O(1)$ ((esta complejidad $O(1)$ es en realidad amortizada, pero eso no afecta nuestro análisis)). | + | La pregunta que nos hacemos es, ¿Cuál es la complejidad de estas dos operaciones? La operación 1, de agregar, es la más simple, pues consistirá de un único ''.push()'' en el stack, que ya sabemos que tiene complejidad $O(1)$ ((Esta complejidad $O(1)$ es en realidad amortizada, pero eso no afecta nuestro análisis)). |
| Si hacemos un análisis de cuánto tarda la operación de sacar, en el peor caso podrían tener que sacarse muchos números, pues la cantidad que se saca depende del $k$ ingresado. En particular, $k$ podría ser tan grande como todos los elementos que se han agregado en la pila hasta el momento. Por lo tanto en el peor de los casos la operación 2 tiene un costo $O(N)$, siendo $N$ la cantidad de elementos que se agregan en total (es decir, la cantidad de operaciones de tipo 1). | Si hacemos un análisis de cuánto tarda la operación de sacar, en el peor caso podrían tener que sacarse muchos números, pues la cantidad que se saca depende del $k$ ingresado. En particular, $k$ podría ser tan grande como todos los elementos que se han agregado en la pila hasta el momento. Por lo tanto en el peor de los casos la operación 2 tiene un costo $O(N)$, siendo $N$ la cantidad de elementos que se agregan en total (es decir, la cantidad de operaciones de tipo 1). | ||
| 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.1511474436.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
