Análisis de algoritmos

Complejidad amortizada Dra. Elisa Schaeffer [email protected]

PISIS / FIME / UANL

Complejidad amortizada– p. 1

Complejidad amortizada

La idea en el análisis de complejidad amortizada es definir una sucesi´ on de n operaciones y estimar una cota superior para su tiempo de ejecución. Esta cota superior está dividido por el número de operaciones n para obtener la complejidad amortizada (inglés: amortized complexity) de una operación. No es necesario que las operaciones de la sucesión sean iguales ni del mismo tipo.

Complejidad amortizada– p. 2

Motivación

La motivación de complejidad amortizada es poder “pronósticar” con mayor exactitud el tiempo de ejecución del uso del algoritmo en el “mundo real”. Si uno típicamente quiere realizar ciertos tipos de cosas, ¿cuánto tiempo toma?

Complejidad amortizada– p. 3

Formalmente

Sea D0 el estado inicial de una estructura de datos. En cada momento, se aplica una operación O. Después de i operaciones: Di . Sucesión de operaciones como O1 , . . . , On . El “costo” computacional de operación Oi puede ser muy distinto del costo de otra operación Oj .

Complejidad amortizada– p. 4

Costo promedio

La idea es sumar los costos y pensar en términos de “costo promedio”. Para que tenga sentido ese tipo de análisis, la sucesión de operaciones estudiada tiene que ser la peor posible. Si no lo es, no hay guarantía ninguna que se pueda generalizar el análisis para sucesiones más largas.

Complejidad amortizada– p. 5

Arreglos dinámicos

Como un ejemplo, evaluamos la complejidad de operar un arreglo din´amico. Se duplica el tamaño siempre cuando hace falta añadir un elemento. Se corta el tamaño a mitad cuando se ha liberado tres cuartas partes del espacio.

Complejidad amortizada– p. 6

Una sucesión de inserciones

Evaluamos la sucesión de 2k inserciones en tal arreglo. Al realizar la primera inserción, se crea un arreglo de un elemento. Con la segunda, se duplica el tamaño para lograr a guardar el segundo elemento. En práctica, esto significa que se reserva un arreglo nuevo del tamaño doble en otra parte y mueve cada clave que ya estaba guadrara en el arreglo al espacio nuevo. Con la tercera inserción, se crea espacio para dos elementos más, etcétera. Complejidad amortizada– p. 7

Baratas versus caras

Entonces, con la sucesión de operaciones definida, vamos a tener que multiplicar el tamaño del arreglo k veces y las otras 2k − k inserciones van a ser “baratas”. La complejidad de una inserción barata es O (1). Cuando el tamaño del arreglo es n, el costo de duplicar su tamaño es O (n). Entonces, la complejidad de una inserción “cara” es O (1) + O (n) ∈ O (n). Para la inserción difícil número i, el tamaño va a ser 2i .

Complejidad amortizada– p. 8

Suma total

La suma de la complejidad de las k inserciones difíciles es ! k X
i k+1 . 2 =O 2 O i=1

k La complejidad total de los 2 − k operaciones fáciles es

O 2k − k ∈ O 2k porque cada una es de tiempo constante. k =⇒ La complejidad de la sucesión completa de 2

k+1 k k inserciones es O 2 +2 ∈O 3·2 .

Complejidad amortizada– p. 9

Complejidad amortizada

Dividimos la complejidad total por el número de operaciones 2k para obtener la complejidad amortizada por operación:   k 3·2 O = O (3) ∈ O (1) . k 2 Si hacemos n operaciones y cada uno tiene complejidad amortizada constante, cada sucesión de puras inserciones tiene complejidad amortizada lineal, O (n).

Complejidad amortizada– p. 10

Análisis con eliminaciones

Para poder incluir las eliminaciones en el análisis, hay que cambiar la técnica de análisis. Utilizamos el m´etodo de potenciales, también conocido como el método de cuentas bancarias, donde se divide el costo de operaciones caras entre operaciones más baratas.

Complejidad amortizada– p. 11

Método de potenciales

Supone que al comienzo nos han asignado una cierta cantidad M de pesos. Cada operación básica de tiempo constante O (1) cuesta un peso. Vamos a realizar n operaciones.

Complejidad amortizada– p. 12

Costo planeado

El costo

planeado de una operación Oi es pi =

M n

pesos.

Si una operación no necesita todos sus M pesos n asignados, los ahorramos en una cuenta bancaria común.

Complejidad amortizada– p. 13

Costo planeado

El costo

planeado de una operación Oi es pi =

M n

pesos.

Si una operación no necesita todos sus M pesos n asignados, los ahorramos en una cuenta bancaria común. Si una operación necesita más que M pesos, la n operación puede retirar fondos adicionales de la cuenta bancaria.

Complejidad amortizada– p. 13

Costo planeado

El costo

planeado de una operación Oi es pi =

M n

pesos.

Si una operación no necesita todos sus M pesos n asignados, los ahorramos en una cuenta bancaria común. Si una operación necesita más que M pesos, la n operación puede retirar fondos adicionales de la cuenta bancaria. Si en la cuenta no hay balance, la operación los toma prestados del banco.

Complejidad amortizada– p. 13

Costo planeado

El costo

planeado de una operación Oi es pi =

M n

pesos.

Si una operación no necesita todos sus M pesos n asignados, los ahorramos en una cuenta bancaria común. Si una operación necesita más que M pesos, la n operación puede retirar fondos adicionales de la cuenta bancaria. Si en la cuenta no hay balance, la operación los toma prestados del banco. Todo el préstamo habrá que pagar con lo que ahorran operaciones que siguen. Complejidad amortizada– p. 13

Balance = potencial

Denotamos el balance de la cuenta después de la operación número i, o sea, en el estado Di , con Φi . El balance también se llama la potencial de la estructura.

La meta: poder mostrar que la estructura siempre contiene “la potencial suficiente” para poder pagar la operaciones que vienen.

Complejidad amortizada– p. 14

Costo amortizado

Sea ri el costo El costo

real de la operación Oi .

amortizado de la operación Oi es

ai = ti + Φi − Φi−1 | {z } pesos ahorrados

Complejidad amortizada– p. 15

Costo amortizado total

El costo amortizado total de las n operaciones es A=

n X i=1

ai

n X (ri + Φi − Φi−1 ) =

= =

i=1 n X

i=1 n X

n X (Φi − Φi−1 ) ri + i=1

ri + Φn − Φ0 ,

i=1

=⇒ Costo real total: R =

n X i=1

r1 = Φ0 − Φn +

n X

ai .

i=1

Complejidad amortizada– p. 16

Función de balance

Para poder realizar el análisis, primero hay que asignar los costos planeados pi . Después de que se intenta definir una funci´ on de balance Φi : N → R tal que el costo amortizado de cada operación es menor o igual al costo planeado: ai = ri + Φi − Φi−1 ≤ pi .

Complejidad amortizada– p. 17

Consecuencias

Con tales costos amortizados, aplica n X

ri ≤ Φ0 − Φn +

n X

pi .

i=1

i=1

La transacción con el banco (ahorro o préstamo) de la operación Oi es de pi − ri pesos. Típicamente queremos que Φi ≥ 0 para cada estado Di . Si esto aplica, tenemos n X i=1

ri ≤ Φ0 +

n X

pi .

i=1

Complejidad amortizada– p. 18

Exactitud

Comúnmente además tenemos que Φ0 = 0, en cual caso la suma de los costos planeados es una cota superior a la suma de los costos reales. Si uno elige costos planeados demasiado grandes, la cota será cruda y floja y la estimación de la complejidad no es exacta. Haber elegido un valor demasiado pequeño de los costos planeados, resulta imposible encontrar una función de balance apropiada.

Complejidad amortizada– p. 19

Precio de una inserción

Hay que asegurar que el precio de una inserción cara se pueda pagar con lo que han ahorrado las inserciones baratas anteriores. Suponemos que el tiempo de una inserción fácil sea t1 y el tiempo de mover una clave al espacio nuevo (de tamaño doble) sea t2 . Entonces, si antes de la inserción cara, la estructura contiene n claves, el precio real total de la inserción cara es t1 + nt2 .

Complejidad amortizada– p. 20

Función de balance

Vamos a definir una función de balance tal que su valor inicial es cero y también su valor después de hacer duplicado el tamaño es cero. En cualquier otro momento, será Φi > 0. La meta es llegar al mismo resultado del método anterior n X

ri = O (n)

i=1

para tener complejidad amortizada O (1) por operación.

Complejidad amortizada– p. 21

Intento: pi = t1 + 2t2

Habrá que poder pagar el costo de añadir la clave nueva (t1 ) y preparar para mover la clave misma después a un arreglo nuevo de tamaño doble (t2 ) además de preparar mover todas las claves anteriores (uno por elemento, el otro t2 ).

Complejidad amortizada– p. 22

Requisito

∀i : ai = ri + Φi − Φi−1 ≤ pi = t1 + 2t2 . Denotamos por ci el número de claves guardados en el arreglo en el estado Di . Claramente ci = ci−1 + 1.

Complejidad amortizada– p. 23

Intento: Φi = 2t2 ci − t2 ei

ei = el espacio del arreglo después de Oi inserciones fáciles: ei = ei−1 inserciones difíciles: ei = 2ei−1 = 2ci−1

Complejidad amortizada– p. 24

Inserción fácil

ai = t1 + (2t2 (ci−1 + 1) − t2 ei−1 ) − (2t2 ci−1 − t2 ei−1 ) = t1 + 2t2 = pi . El costo amortizado es igual al costo planeado.

Complejidad amortizada– p. 25

Inserción difícil

ai = (t1 + t2 ci−1 ) + (2t2 (ci−1 + 1) − t2 2ci−1 ) − (2t2 ci−1 − t2 ci−1 ) = t1 + 2t2 = pi , Cumple: ai = t1 + 2t2 para todo i.

Complejidad amortizada– p. 26

Eliminaciones Cada inserción tiene costo amortizado O (1) y el costo real de una serie de n operaciones es O (n).

Eliminaciones: si un arreglo de tamaño ei contiene solamente ci ≤ 0,25ei claves, su tamaño será cortado a la mitad: ei+1 = 0,5ei . El costo de la reducción del tamaño es t2 ci , porque habrá que mover cada clave.

Complejidad amortizada– p. 27

Costo de eliminación

Marcamos el precio de una eliminación simple (que no causa un ajuste de tamaño) con t3 . Vamos a cubrir el gasto del reducción por cobrar por eliminaciones que ocurren cuando el arreglo cuenta con menos que 0,5ei claves guardadas en el estado Di .

Complejidad amortizada– p. 28

El ahorro

Entonces, por cada eliminación de ese tipo, ahorramos t2 pesos. Al de reducir el tamaño, hemos ahorrado   emomento i − 1 pesos (nota que ei solamente cambia cuando 4 duplicamos o reducimos, no en operaciones baratas). Ese ahorro paga la eliminación cara.

Complejidad amortizada– p. 29

Función de balance

Elegimos ahora una función de balance definido por partes:  ei    2t2 ci − t2 ei , si ci ≥ 2 , Φi =    e1 t2 − t2 ci , si ci < ei . 2 2

Complejidad amortizada– p. 30

El caso de inserciones ei Para el caso ci > , no cambia nada a la situación anterior 2 ni para inserciones baratas ni para las caras: ai = t1 + 2t2 . ei Para el otro caso ci < , tenemos 2 ai = ri + Φ i − Φi−1    t2 e i t2 ei−1 = t1 + − t 2 ci − − t2 ci−1 2 2 = t1 − t2 , porque para estas inserciones, siempre tenemos ei = ei−1 y son siempre baratas (nunca causan que se duplique el espacio). Complejidad amortizada– p. 31

Inserciones cuando “cambia” Φ ei El caso donde ci = : 2 ai = ri + Φi − Φi−1



t2 ei−1 = t1 + (2t2 ci − t2 ei ) − − t2 ci−1 2 = t1 + 2t2 ci − 2t2 ci − t2 ci + t2 (ci − 1) = t1 − t2 .



Complejidad amortizada– p. 32

ei Eliminaciones baratas: ci ≥ 2

ai = = = =

ri + Φi − Φi−1 t3 + (2t2 ci − t2 ei ) − (2t2 ci−1 − t2 ei−1 ) t3 + 2t2 (ci−1 − 1) − 2t2 ci−1 t3 − 2t2 .

Complejidad amortizada– p. 33

Eliminaciones al “cambio” de Φ ei Con ci = − 1: 2 ai = ri + Φ i − Φi−1  t2 e i = t3 + − t2 ei − (2t2 ei−1 − t2 ei ) 2 3t2 ei = t3 + − t2 (ei−1 − 1) − 2t2 ci−1 2 = t3 + 3t2 ci−1 − t2 ei−1 + t2 − 2t2 ci−1 = t3 + t2 .

Complejidad amortizada– p. 34

Caso de ahorro ei e1 − 1 mientras ci−1 ≥ + 1: ci < 2 4 ai = ri + Φ i − Φi−1    t2 e i 1 t2 ei−1 = t3 + − t 2 ci − − t2 ci−1 2 2 = t3 − t2 (ci−1 − 1) + t2 ci−1 = t3 + t2 .

Complejidad amortizada– p. 35

Eliminaciones con ci−1

ei−1 = 4

ai = ri + Φ  i − Φi−1   t2 ei−1 t2 e i − − t2 ci−1 = t 3 + t 2 ci − 2 2 t2 ei−1 t2 ei−1 = t3 + − + t2 ci−1 4 2 t2 ei−1 t2 ei−1 + = t3 − 4 4 = t3 .

Complejidad amortizada– p. 36

Resumen

En todos los casos llegamos a tener una complejidad amortizada constante O (1) por operación. =⇒ La complejidad de cualquier combinación de n inserciones y/o eliminaciones, la complejidad amortizada total es O (n).

Complejidad amortizada– p. 37

Invariante de costo

La regla general de poder lograr la meta de “siempre poder pagar las operaciones que quedan de hacer” es asegurar que se mantenga un invariante de costo (inglés: credit invariant) durante toda la sucesión.

Complejidad amortizada– p. 38

Invariante del ejemplo

ei 1. Si ci = , el balance Φi es cero. 2 e ei  i 2. Si ≤ ci < , el balance Φi es igual a la cantidad 4 2 de celdas libres en las posiciones de la segunda cuarta parte del arreglo. ei 3. Si ci > , el balance Φi es igual a dos veces la 2 cantidad de claves guardados en las posiciones de la segunda mitad del arreglo.

Complejidad amortizada– p. 39

Árboles biselados

n m

= la cantidad de claves guardadas en el árbol = el número de operaciones realizados al árbol

Queremos mostrar que la complejidad amortizada de cualquier sucesión de m operaciones es O (m log n).

Complejidad amortizada– p. 40

Costo planeado

Marcamos con R(v) el ramo la raíz de cual es el vértice v y con |R(v)| el número de vértices en el ramo (incluyendo a v). Sea r la raíz del árbol completo. Definimos µ(v) = ⌊log |R(v)|⌋. El costo planeado de las operaciones será pi = O (log n) = O (log |R(r)|) = O (µ(r)) .

Complejidad amortizada– p. 41

splay

Cada operación constituye de un número constante de operaciones splay y un número constante de operaciones simples. =⇒ basta con establecer que la complejidad amortizada de una operación splay es O (µ(r)).

Complejidad amortizada– p. 42

Cuentas bancarias

Pensamos en este caso que cada vértice del árbol tiene una cuenta propia, pero el balance está en uso de todos. Mantenemos el siguiente invariante de costo: cada vértice v siempre tiene por lo menos µ(v) pesos en su propia cuenta.

Complejidad amortizada– p. 43

Teorema

Cada operación splay(v, A) requiere al máximo (3 (µ(A) − µ(v)) + 1) unidades de costo para su aplicación y la actualización del invariante de costo.

Complejidad amortizada– p. 44

Demostración

splay consiste de una sucesión de rotaciones. En el caso que el vértice u que contiene la llave de interés tenga un padre t, pero no un abuelo, hace falta una rotación simple derecha.

Complejidad amortizada– p. 45

Caso 1: sin abuelo

Aplica µdespués(u) = µantes (t) µdespués(t) ≤ µdespués(u) Mantener el invariante cuesta: µdespués (u) + µdespués(t) − (µantes (u) + µantes t)) = µdespués(t) − µantes (u)) ≤ µdespués(u) − µantes (u). El peso que sobra se gasta en las operaciones de tiempo constante y cantidad constante por operación splay (comparaciones, actualizaciones de punteros, etcétera). Complejidad amortizada– p. 46

Caso 2: con abuelo

En el segundo caso, u tiene el padre t y un abuelo t′ . Hay que hacer dos rotaciones derechas — primero para mover t al lugar del abuelo, empujando el abuelo abajo a la derecha y después para mover u mismo al lugar nuevo del padre. El costo total de mantener el invariante es T = µdespués(u) + µdespués(t) + µdespués(t′ ) −µantes (u) − µantes (t) − µantes (t′ ).

Complejidad amortizada– p. 47

Caso 2 cont.

Por la estructura de la rotación aplica que µdespués(u) = µantes (t′ ), por lo cual T = = ≤ =

µdespués(t) + µdespués(t′ ) − µantes (u) − µantes (t) (µdespués(t) − µantes (u)) + (µdespués(t′ ) − µantes (t)) (µdespués(u) − µantes (u)) + (µdespués(u) − µantes (u)) 2 (µdespués(u) − µantes (u)) .

Complejidad amortizada– p. 48

Detalles

Si logramos tener µdespués(u) > µantes (u), nos queda por lo menos un peso para ejecutar la operación. Hay que analizar el caso que µdespués(x) = µantes (x). Necesitamos asegurarnos que T ≤ 0, o sea, no nos cuesta nada mantener el invariante válido. (La derivación será un ejercicio.)

Llegamos a µdespués(u) = µantes (u), por lo cual T < 0. El tercer caso de splay es una rotación doble izquierda-derecha. Omitimos sus detalles. Complejidad amortizada– p. 49

Resumen

al insertar, asignar O (log n) pesos al elemento al unir, se asigna a la raíz nueva O (log n) pesos cada operación puede gastar O (log n) pesos en ejecutar las operaciones splay el mantenimiento del invariante de costo y las operaciones adicionales que se logra en tiempo O (1) =⇒ cada operación tiene costo amortizado O (log n) =⇒ la complejidad amortizada de una sucesión de m operaciones es O (m log n)

Complejidad amortizada– p. 50

Montículos de Fibonacci

Invariante de costo: cada raíz tiene un peso y cada vértice marcado tiene dos pesos. Los costos planeados de inserción, decrementación del valor de clase y unir dos montículos son un peso por operación. La eliminación del mínimo tiene costo planeado de O (log n) pesos.

Complejidad amortizada– p. 51

Insertar una clave

Lo único que se hace es crear una raíz nueva con la clave nueva y un peso. Esto toma tiempo constante O (1).

Complejidad amortizada– p. 52

Disminuir una clave

Movemos el vértice con la clave a la lista de raíces en tiempo O (1) junto con un peso. Si el padre está marcado, su movimiento a la lista de raízes se paga por el peso extra que tiene el vértice marcado — también se le quita la marca por la operación, por lo cual no sufre el invariante. El otro peso el vértice padre lleva consigo. Si hay que marcar el abuelo, hay que añadirle dos pesos. El tiempo total es constante, O (1).

Complejidad amortizada– p. 53

Unir dos montículos

Simplemente unimos las listas de raíces. Por la contracción de las listas que se realiza al eliminar el mínimo, el costo de esta operación es O (1). Esta operación no causa ningún cambio en el invariante. Hay que tomar en cuenta que estamos pensando que las listas de raíces están implementadas como listas enlazadas, por lo cual no hay que copiar nada, solamente actualizar unos punteros.

Complejidad amortizada– p. 54

Eliminar el mínimo

La operación en sí toma tiempo O (1). Además depositamos un peso en cada hijo directo del vértice eliminado. Contracción de la lista de raíces: Gastamos los pesos de las raíces mismas. Después depositamos de nuevo un peso en cada raíz. Son O (log n) raíces. =⇒ Complejidad amortizada O (log n).

Complejidad amortizada– p. 55

Eliminar elemento cualquiera

Primero reducir su valor a −∞. Después quitando el mínimo. Esto toma tiempo O (1) + O (log n) ∈ O (log n).

Complejidad amortizada– p. 56

Complejidad de estructuras

Oper.

L

A

M

B

F

Inser.

Θ (n)

O (log n)

O (log n)

O (log n)

O (1)

Ubic. mín.

O (1)

O (1)

O (1)

O (log n)

O (1)

Elim. mín.

O (1)

O (log n)

O (log n)

O (log n)

O (log n) ∗

Elim.

O (1)

O (log n)

O (log n)

O (log n)

O (log n) ∗

Dism.

Θ (n)

O (log n)

O (log n)

O (log n)

O (1) ∗

Unir

Θ (n)

Θ (n)

Ω (n)

O (log n)

O (1)

Listas (L), árboles balanceados (A), montículos (M), montículos binomiales (B) y montículos de Fibonacci (F). Las complejidades amortizadas llevan un asterisco (∗ ).

Complejidad amortizada– p. 57

Tarea para entregar el martes

Demuestra que en el análisis de a´ rboles biselados, de los suposiciones µdespués(u) = µantes (u) y µdespués(u) + µdespués(t) + µdespués(t′ ) ≥ µantes (u) + µantes (t) + µantes (t′ ) t siendo el padre de u y t′ el abuelo de u y la operación siendo rotación doble derecha, se llega a una contradicci´on.

Complejidad amortizada– p. 58