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 Última revisión Ambos lados, revisión siguiente | ||
|
algoritmos-oia:analisis-amortizado [2017/11/23 21:59] santo |
algoritmos-oia:analisis-amortizado [2017/11/23 22:00] 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á en 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). | ||
algoritmos-oia/analisis-amortizado.txt · Última modificación: 2017/11/23 22:02 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
