algorithm - ¿Complejidad amortizada en términos simples?

amortized-analysis

Question

¿Alguien puede explicar la complejidad amortizada en términos simples? He estado teniendo dificultades para encontrar una definición precisa en línea y no sé cómo se relaciona por completo con el análisis de algoritmos. Cualquier cosa útil, incluso si se hace referencia externa, sería muy apreciada.

Answer 1

En un análisis amortizado, el tiempo requerido para realizar una secuencia de operaciones de estructura de datos se promedia sobre todas las operaciones realizadas ... El análisis amortizado difiere del análisis de casos promedio en que la probabilidad no está involucrada; un análisis amortizado garantiza el rendimiento promedio de cada operación en el peor de los casos.

(de Cormen et al., "Introducción a los algoritmos")

Eso podría ser un poco confuso, ya que dice que el tiempo se promedia y que no es un análisis de caso promedio. Entonces, permítanme intentar explicar esto con una analogía financiera (de hecho, "amortizado" es una palabra comúnmente asociada con la banca y la contabilidad).

Supongamos que está operando una lotería. (No compraremos un boleto de lotería, al cual llegaremos en un momento, pero operando la lotería en sí.) Imprime 100.000 boletos, que venderá por 1 unidad monetaria cada uno. Uno de esos tickets dará derecho al comprador a 40,000 unidades monetarias.

Ahora, suponiendo que pueda vender todas las entradas, puede ganar 60,000 unidades monetarias: 100,000 unidades monetarias en ventas, menos el premio de 40,000 unidades monetarias. Para usted, el valor de cada boleto es de 0.60 unidades monetarias, amortizado sobre todos los boletos. Este es un valor confiable; puedes confiar en eso. Si te cansas de vender los boletos tú mismo, y alguien viene y te ofrece venderlos por 0,30 unidades de moneda cada uno, sabes exactamente dónde estás parado.

Para el comprador de lotería, la situación es diferente. El comprador tiene una pérdida esperada de 0.60 unidades monetarias cuando compra un boleto de lotería. Pero eso es probabilístico: el comprador podría comprar diez boletos de lotería todos los días durante 30 años (un poco más de 100.000 boletos) sin ganar jamás. O podrían comprar un boleto de manera espontánea un día y ganar 39.999 unidades monetarias.

Aplicado al análisis de la estructura de datos, estamos hablando del primer caso, donde amortizamos el costo de alguna operación de estructura de datos (por ejemplo, insertar) sobre todas las operaciones de ese tipo. El análisis de casos promedio trata del valor esperado de una operación estocástica (por ejemplo, búsqueda), donde no podemos calcular el costo total de todas las operaciones, pero podemos proporcionar un análisis probabilístico del costo esperado de uno solo.

A menudo se afirma que el análisis amortizado se aplica a la situación en la que una operación de alto costo es rara, y ese es a menudo el caso. Pero no siempre. Considere, por ejemplo, la llamada "cola del banquero", que es una cola FIFO (primero en entrar, primero en salir), hecha de dos pilas. (Es una estructura de datos funcional clásica: puede construir pilas de LIFO baratas a partir de nodos de enlace único inmutables, pero los FIFO baratos no son tan obvios). Las operaciones se implementan de la siguiente manera:

put(x): Push x on the right-hand stack.
y=get(): If the left-hand stack is empty:
Pop each element off the right-hand stack and
push it onto the left-hand stack. This effectively
reverses the right-hand stack onto the left-hand stack.
Pop and return the top element of the left-hand stack.

Ahora, afirmo que el costo amortizado de put y get es O(1) , suponiendo que comienzo y termino con una cola vacía. El análisis es simple: siempre put en la pila de la mano derecha y get de la pila de la mano izquierda. Así que aparte de la cláusula If , cada put es un push , y cada get es pop , ambos son O(1) . No sé cuántas veces ejecutaré la cláusula If -depende del patrón de put y get s-, pero sé que cada elemento se mueve exactamente una vez desde la pila de la derecha hasta la pila de la izquierda . Entonces, el costo total sobre toda la secuencia de n put s y n get s es: n push es, n pop s, y n move s, donde un move es pop seguido de un push : en otras palabras, 2n put sy get el resultado en 2n push es y 2n pop s. Por lo tanto, el costo amortizado de una put única (u get ) es de un solo push y de una sola vez.

Tenga en cuenta que las colas bancarias se llaman así precisamente por el análisis de complejidad amortizado (y la asociación de la palabra "amortizado" con las finanzas). Las colas de los banqueros son la respuesta a lo que solía ser una pregunta de entrevista común, aunque creo que ahora se la considera demasiado conocida: invente una cola que implemente las siguientes tres operaciones en tiempo O (1) amortizado:

1) Obtener y eliminar el elemento más antiguo de la cola

2) Ponga un nuevo elemento en la cola,

3) Encuentra el valor del elemento máximo actual.

Answer 2

El principio de "complejidad amortizada" es que aunque algo puede ser bastante complejo cuando lo haces, ya que no se realiza con mucha frecuencia, se considera "no complejo". Por ejemplo, si crea un árbol binario que necesita equilibrar de vez en cuando -digamos una vez cada 2^n inserciones- porque aunque equilibrar el árbol es bastante complejo, solo ocurre una vez en cada n inserciones (por ejemplo, una vez en el número de inserción 256, luego nuevamente en 512th, 1024th, etc.). En todas las demás inserciones, la complejidad es O (1) - sí, toma O (n) una vez cada n inserciones, pero es solo 1/n probabilidad - así que multiplicamos O (n) por 1 / ny obtenemos O (1 ) Entonces se dice que es "Complejidad amortizada de O (1)", porque a medida que agrega más elementos, el tiempo consumido para reequilibrar el árbol es mínimo.

Answer 3

Es algo similar a la multiplicación de la complejidad del peor caso de diferentes ramas en un algoritmo con la probabilidad de ejecutar esa rama y agregar los resultados. Entonces, si es poco probable que se tome alguna rama, contribuye menos a la complejidad.

Answer 4

Medios amortizados divididos en ejecuciones repetidas. Se garantiza que el peor de los casos no ocurrirá con mucha frecuencia. Por ejemplo, si el caso más lento es O (N), pero la posibilidad de que eso ocurra es solo O (1 / N), y de lo contrario el proceso es O (1), entonces el algoritmo todavía habría amortizado el tiempo O (1) constante . Simplemente considere que el trabajo de cada ejecución de O (N) se parcelará en N otras ejecuciones.

El concepto depende de tener suficientes carreras para dividir el tiempo total. Si el algoritmo solo se ejecuta una vez, o tiene que cumplir un plazo cada vez que se ejecuta, entonces la complejidad del caso más desfavorable es más relevante.

Answer 5

Digamos que está tratando de encontrar el k-ésimo elemento más pequeño de una matriz no ordenada. Ordenar la matriz sería O (n logn). Entonces, encontrar el k-ésimo número más pequeño es solo ubicar el índice, entonces O (1).

Como la matriz ya está ordenada, nunca tendremos que volver a ordenar. Nunca abordaremos el peor de los casos más de una vez.

Si realizamos n consultas para tratar de localizar kth más pequeño, seguirá siendo O (n logn) porque domina sobre O (1). Si promediamos el tiempo de cada operación, será:

(n logn) / n o O (logn). Entonces, Complejidad del Tiempo / Número de Operaciones.

Esto es complejidad amortizada.

Creo que así es como va, estoy aprendiéndolo también ...

Answer 6

La complejidad amortizada es el gasto total por operación, evaluado en una secuencia de operaciones.

La idea es garantizar el gasto total de la secuencia completa, al tiempo que permite que las operaciones individuales sean mucho más costosas que el costo amortizado.

Ejemplo:
El comportamiento de C ++ std::vector<> . Cuando push_back() aumenta el tamaño del vector por encima de su valor preasignado, dobla la longitud asignada.

Por lo tanto, un solo push_back() puede tomar O(N) tiempo para ejecutarse (ya que los contenidos del array se copian a la nueva asignación de memoria).

Sin embargo, dado que el tamaño de la asignación se duplicó, las siguientes llamadas N-1 a push_back() tomarán O(1) vez para ejecutarse. Entonces, el total de N operaciones aún tomará O(N) tiempo; dando así push_back() un costo amortizado de O(1) por operación.

A menos que se especifique lo contrario, la complejidad amortizada es una garantía asintótica del peor caso para cualquier secuencia de operaciones. Esto significa:

• Al igual que con la complejidad no amortizada, la notación de gran O utilizada para la complejidad amortizada ignora tanto la sobrecarga inicial fija como los factores de rendimiento constantes. Por lo tanto, para evaluar el rendimiento amortizado de gran O, generalmente puede suponer que cualquier secuencia de operaciones amortizadas será "lo suficientemente larga" como para amortizar un gasto de inicio fijo. Específicamente, para el ejemplo std::vector<> , esta es la razón por la cual no necesita preocuparse acerca de si realmente encontrará N operaciones adicionales: la naturaleza asintótica del análisis ya asume que lo hará.

• Además de la longitud arbitraria, el análisis amortizado no hace suposiciones sobre la secuencia de operaciones cuyo costo está midiendo: es la garantía más desfavorable para cualquier secuencia posible de operaciones. No importa qué tan mal se escojan las operaciones (¡por ejemplo, un adversario malicioso!), Un análisis amortizado debe garantizar que una secuencia de operaciones suficientemente larga no cueste consistentemente más que la suma de sus costos amortizados. Esta es la razón por la cual (a menos que se lo mencione específicamente como un calificador) "probabilidad" y "caso promedio" no son relevantes para el análisis amortizado, ¡más de lo que lo son para un análisis de big-O del peor caso ordinario!