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 21:44] santo [Ejemplo: contador binario] |
algoritmos-oia:analisis-amortizado [2017/11/23 22:02] (actual) santo |
||
|---|---|---|---|
| Línea 8: | Línea 8: | ||
| Varias operaciones de las bibliotecas estándar, como la [[cpp-avanzado:stl|STL de C++]], garantizan sus tiempos de ejecución en forma amortizada, como por ejemplo ''.push_back()'' de ''vector'' que tiene un tiempo de ejecución $O(1)$ amortizado. | Varias operaciones de las bibliotecas estándar, como la [[cpp-avanzado:stl|STL de C++]], garantizan sus tiempos de ejecución en forma amortizada, como por ejemplo ''.push_back()'' de ''vector'' que tiene un tiempo de ejecución $O(1)$ amortizado. | ||
| + | |||
| + | ===== Ejemplo: pila con eliminación múltiple ===== | ||
| + | |||
| + | Este es quizás uno de los ejemplos más comunes e importantes de la idea de análisis amortizado. | ||
| + | |||
| + | Supongamos que tenemos una pila, como podría ser por ejemplo [[cpp-avanzado:queue-y-stack|stack]] de la STL de C++. Comenzando con una pila vacía, vamos a realizarle **dos tipos de operaciones**: | ||
| + | |||
| + | - Agregar un cierto elemento $x$ a la pila. | ||
| + | - Sacar una cierta cantidad $k$ de elementos de la pila. | ||
| + | |||
| + | 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)). | ||
| + | |||
| + | 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). | ||
| + | |||
| + | Entonces por ejemplo, si se hacen $1000$ operaciones de tipo $1$, y $1000$ operaciones de tipo $2$, como las operaciones de tipo $2$ pueden costar hasta $1000$ según nuestro análisis previo, el costo total de estas operaciones será como mucho $1000 \cdot 1000$ en el peor de los casos. | ||
| + | |||
| + | Si bien este análisis es correcto, es **pesimista**: En realidad el costo total será siempre **muchísimo menor** que $1000 \cdot 1000$. Observemos que, para que el costo total sea tan grande, **todas** las operaciones de tipo 2 deberían ser caras, es decir, en **todas** ellas se deberían eliminar **todos** los números. Pero esto es imposible: Una vez que un número fue eliminado, ya no está en la pila, y no puede "ser eliminado de nuevo". En otras palabras, **cada número que se agrega con una operación tipo 1, puede ser borrado a lo sumo una vez, en una sola operación tipo 2**. | ||
| + | |||
| + | Con eso en mente, podemos pensar el costo **total** de otra manera: En lugar de pensar cuánto cuesta hacer los borrados en **una** operación particular, pensamos cuántas veces se borra un cierto **elemento** particular. La observación es entonces que, sin importar en qué operación se borre, cada elemento que se agrega se borra como máximo **una única vez**, y entonces el costo total de los borrados es proporcional a la cantidad de elementos agregados, es decir, a la cantidad de operaciones de tipo 1. | ||
| + | |||
| + | Si llamamos $N$ al total de operaciones (tanto de tipo 1 como de tipo 2), tenemos entonces resumiendo: | ||
| + | |||
| + | - 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 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)$. | ||
| + | - 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. | ||
| ===== Ejemplo: contador binario ===== | ===== Ejemplo: contador binario ===== | ||
| Línea 92: | Línea 120: | ||
| $$T = 2^{N-1} \cdot 1 + 2^{N-2} \cdot 2 + 2^{N-3} \cdot 3 + \cdots + 1 \cdot N$$ | $$T = 2^{N-1} \cdot 1 + 2^{N-2} \cdot 2 + 2^{N-3} \cdot 3 + \cdots + 1 \cdot N$$ | ||
| - | Como estamos realizando $2^N$ operaciones en total, el costo **por operación** se obtiene dividiendo al anterior por $2^N$, y entonces el costo **promedio** es: | + | Como estamos realizando $n_{ops}=2^N$ operaciones en total, el costo **por operación** se obtiene dividiendo al anterior por $2^N$, y entonces el costo **promedio** es: |
| - | $$\frac{T}{n_{ops}} = \frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + \frac{5}{32} + \cdots + \frac{1}{2^N} \leq 2$$ | + | $$\frac{T}{n_{ops}} = \frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + \frac{5}{32} + \cdots + \frac{N}{2^N} \leq 2$$ |
| FIXME [Linkear a alguna explicación de por qué esa suma no se pasa de 2] | FIXME [Linkear a alguna explicación de por qué esa suma no se pasa de 2] | ||
| Línea 105: | Línea 133: | ||
| Algo muy similar a esto ocurre con la función [[cpp-avanzado:algorithm:next-permutation|next_permutation]], que si se utiliza muchas veces para generar todas las permutaciones de una lista dada, tiene una complejidad amortizada $O(1)$. | Algo muy similar a esto ocurre con la función [[cpp-avanzado:algorithm:next-permutation|next_permutation]], que si se utiliza muchas veces para generar todas las permutaciones de una lista dada, tiene una complejidad amortizada $O(1)$. | ||
| - | |||
| - | ===== Ejemplo: pila con eliminación múltiple ===== | ||
algoritmos-oia/analisis-amortizado.1511473480.txt.gz · Última modificación: 2017/11/23 21:44 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
