*Análisi amortizado* de algoritmos y estructuras de datos
Jérémy Barbay 7 Oct 201007/10/10 a las 13:38 hrs.2010-10-07 13:38:07
*Análisi amortizado* de algoritmos y estructuras de datos
=========================================================
Author: Jérémy Barbay
Date: 2010-10-07 17:36:41 XXX
SCHEDULED: <2010-10-07 Thu 12:00-13:30>
Table of Contents
=================
1 Análisis amortizada
2 Colas de Prioridades
1 Análisis amortizada
~~~~~~~~~~~~~~~~~~~~~~
* Costo Amortizado:
- Se tiene una secuencia de n operaciones con costos
c1,c2,...,cn. Se quiere determinar C=\sum c_i.
- Se puede tomar el peor caso de ci\leq t para tener una
cota superior de C\leq t n.
- Un mejor análisis puede analizar el costo amortizado,
con varias técnicas:
- análisis agragada
- contabilidad de costos
- función potencial.
* Ejemplo simple: Incremento binario
- Incrementar n veces un numero binario de k bits,
- e.g. desde cero hasta 2^k-1, con n=2^k.
- costo \leq k n (brute force)
- costo \leq n + n/2 + ... \leq 2n (costo amortizado)
- La técnica usada aquí es la contabilidad de costos:
- un flip de 0 a 1 cuesta 2
- un flip de 1 a 0 cuesta 0
- cada incremento cuesta 2.
* Función Potencial para contar el costo
- \phi_0 = 0
- \phi_i es el tamaño de la bolsa luego de ejecutar c_1,\ldots,c_i
- \Delta \phi_i = \phi_i - \phi_{i-1}
- costo amortizado = \overline{c_i} = c_i + \Delta\phi_i
- \sum \overline{c_i} = \sum c_i + \phi_n -\phi_0 \geq \sum c_i
- Ejemplo : la analisis del algoritmo para min y max al mismo tiempo.
* En el ejemplo de Incrementacion binaria:
- \phi = cantidad de unos en el numero
- \phi_0 = 0
- c_i = l+1 cuando hay l unos
- \Delta \phi_i = -l+1
- \sum \overline{c_i} = \sum c_i + \phi_n -\phi_0
\geq 2
* Ejemplo: realocación amortizada
- considera el tipo "Vector" en Java.
- de tamaño fijo n
- cuando accede a n+1, crea un otro arreglo de tamaño 2n, y
copia todo.
- cual es el costo amortizado si agregando elementos uno a
uno?
2 Colas de Prioridades
~~~~~~~~~~~~~~~~~~~~~~~
* REFERENCIA: [www.leekillough.com/heaps/]
* Problema: Dado un conjunto (dinámica) de $n$ tareas con
valores, elegir y remudar la tarea de valor máxima.
* operaciones básicas:
- M.build({e1,e2,...,2n})
- M.insert(e)
- M.min
- M.deleteMin
* operaciones adicionales ("Addressable priority queues")
- M.insert(e), volviendo un puntero h ("handle") al elemento insertado
- M.remove(h), remudando el elemento especificado para h
- M.decreaseKey(h,k), reduciendo la llave del elemento especificado para h
- M.merge(Q), agregando el heap Q al heap M.
* Soluciones (conocidas o no):
Linked List Binary Tree (Min-)Heap Fibonacci Heap Brodal Queue [1]
-------------+-------------+---------------+---------------+----------------+------------------
insert O(1) O(log n) O(log n) O(1) O(1)
accessmin O(n) O(1) O(1) O(1) O(1)
deletemin O(n) O(log n) O(log n) O(log n)* O(log n)
decreasekey O(1) O(log n) O(log n) O(1)* O(1)
delete O(n) O(n) O(log n) O(log n)* O(log n)
merge O(1) O(m log(n+m)) O(m log(n+m)) O(1) O(1)
1) Colas de prioridades binarias ("Binary Heaps")
* La solución tradicional
- un arreglo de n elementos
- hijos del nodo i en posiciones 2i y 2i+1
- la valor de cada nodo es mas pequeña que las valores de su hijos.
* Complejidad: Espacio n+O(1), y
Operación Tiempo
-------------------------+----------
M.build({e1,e2,...,2n}) O(n)
M.insert(e) O(\lg n)
M.min O(1)
M.deleteMin O(\lg n)
* Detalles de implementacion (mejorando las constantes)
- Cuidado de no implementar M.build({e1,e2,...,2n}) con n
inserciones (sift up -> O(n\lg n)), pero con n/2
sift-down (-> O(n)).
- En M.deleteMin(), algunas variantes de implementación
(después de cambiar el min con A[n]):
1. dos comparaciones en cada nivel hasta encontrar la
posición final de A[n]
- 2\lg n comparaciones en el peor caso
- \lg n copias
2. una comparación en cada nivel para definir un camino
de tamaño lg n, y una búsqueda binaria para encontrar
la posición final
- \lg n + O(\lg \lg n) comparaciones en el peor caso
- \lg n copias en el peor caso
3. una comparación en cada nivel para definir un camino
de tamaño lg n, y una búsqueda *secuencial* up para encontrar
la posición final
- 2\lg n comparaciones en el peor caso
- \lg n copias en el peor caso
- pero en practica y promedio mucho mejor.
* Flexibilidad de estructuras
+ Porque la complejidad es mejor con un heap que con un
arreglo ordenado?
- Para cada conjunto, hay solamente un arreglo ordenado
que puede representarlo, pero muchos heaps posibles:
eso da mas flexibilidad para la mantención dinámica de
la estructura de datos.
+ Colas de prioridades con punteros ("Addressable priority queues")
- Algún que mas flexible que los arreglos ordenados, las
colas de prioridades binarias todavía son de estructura
muy estricta, por ejemplo para la union de
filas. Estructuras mas flexibles consideran un "bosque"
de arboles. Además, estas estructuras de arboles son
implementadas con puntadores (en ves de implementarlos
en arreglos).
- Hay diferentes variantes. Todas tienen en común los
puntos siguientes:
- un puntero *minPtr* indica el nodo de valor mínima
en el bosque, raíz de alguno arbol.
- *insert* agregas un nuevo arbol al bosque en tiempo O(1)
- *deleteMin* remudas el nodo indicado par minPtr,
dividiendo su arbol en dos nuevos arboles. Buscamos
para el nuevo min y fusionamos algunos arboles (los
detalles diferencian las variantes)
- *decreaseKey(h,k)* es implementado cortando el arbol
al nodo indicado por h, y rebalanceando el arbol
cortado.
- *delete()* es reducido a *decreaseKey(h,0)* y
*deleteMin*
2) "Pairing Heaps"
- Malo rendimiento en el peor caso, pero bastante buena en
practica.
- rebalancea los arboles solamente en deleteMin, y solamente
con pares de raises (i.e. la cantidad de arboles es
reducida por dos a cada deleteMin).
Operación Amortizado
------------------+--------------------------
Insert(C,x) O(1)
Merge O(1)
ExtractMin O(lg n)
decreaseKey(h,k) \Omega(n \lg n \lg\lg n)
3) Colas de prioridades binomiales ("Binomial Heaps")
[en.wikipedia.org/wiki/Binomial_heap]
o p136 de Melhorn y Sanders
* Definición
- Un *arbol binomial* (de orden k) tiene exactamente $k$
hijos de orden distintos k-1,k-2,..., 0. [Un arbol
binomial de orden 0 tiene 0 hijos.]
- Un *bosque binomial* es un conjunto de arboles binomiales
de orden *distintas* (i.e. hay cero o uno arboles de cada
orden).
* Propiedades
- Para cada arbol T
- h(T) \leq lg |T|
- |T| \geq 2^{h(T)}
- Para el bosque
- \forall n hay solamente uno bosque binomial con n nodos.
- al máxima tiene $\lfloor \lg (n+1) \rfloor$ arboles.
- la descomposición del bosque en arboles de orden k
corresponde a la descomposición de n en base de dos.
* Definición
- una *cola binomial* es un bosque binomial donde cada nodo
almacena una clave, y siempre la clave de un padre es
inferior o igual a la clave de un hijo.
* Operaciones
Operación Peor Caso
------------------+-----------
Merge O(lg n)
FindMin O(lg n)
ExtractMin O(lg n)
Insert(C,x) O(lg n)
Heapify O(n)
------------------+-----------
remove(h) O(lg n)
decreaseKey(h,k) O(lg n)
merge(Q) O(lg n)
* Union
- Union de dos arboles binomiales de mismo orden:
- agrega T_2 a T_1 si T_1 tiene la raíz mas pequeña.
- Union de dos bosques binomiales:
- si hay uno arbol de orden k, es lo de la union
- si hay dos arboles de orden k, calcula la union en un arbol de orden k+1
- la propagación es similar a la suma de enteros en binario.
- Complejidad
- O(lg n) en el peor caso
* Insert
- agrega un arbol de orden 0 y hace la union si necesitado
- Complejidad O(log n) en el peor caso
- Puede ser O(1) sin corregir el bosque, que tiene de ser
corregido mas tarde, que puede ser en tiempo O(n) peor
caso, pero sera O(lg n) en tiempo amortizado.
* Mínima
- leí la lista de al máxima $\lfloor \lg (n+1) \rfloor$ raíces
- Complejidad O(lg n)
- Puede ser O(1) si precalculando un puntero al mínima, que
tiene de ser corregido (en tiempo O(\lg n)) a cada modificación.
* DeleteMin
- encontra el min
- remuda el min de su arbol (la raíz)
- reordena su hijos para su orden, en un bosque binomial
- hace la union con el bosque binomial original, menos el arbol del min
- complejidad O(lg n)
* DecreaseKey
- sigue el camino abajo hasta que la condición del heap es
corregida.
- cada arbol tiene altura lg n, entonces la complejidad es
O(lg n) en el peor caso.
* Delete
- reducido a DecreaseKey+DeleteMin
4) Colas de prioridades de Fibonacci ("Fibonacci Heaps")
[en.wikipedia.org/wiki/Fibonacci_heap] o pagina 135 de
Melhorn y Sanders.
* Diferencia con la cola binomial:
- relax la estructura de los arboles (heap-forma), pero de
forma controlada.
- el tamaño de un sub-arbol cual raíz tiene k hijos es al
máxima F_k+2, donde F_k es el k-ésimo numero de
Fibonacci.
* Operaciones
Operación Peor Caso Amortizado
------------------+-----------+------------
Merge O(lg n) O(1)
FindMin O(lg n) O(1)
ExtractMin O(lg n) .
Insert(C,x) O(lg n) O(1)
Heapify O(n) .
------------------+-----------+------------
remove(h) O(lg n) .
decreaseKey(h,k) O(lg n) O(1)
merge(Q) O(lg n) O(1)
5) Overview
(copy de [en.wikipedia.org/wiki/Fibonacci_heap])
Linked List Binary Tree (Min-)Heap Fibonacci Heap Brodal Queue [1]
-------------+-------------+---------------+---------------+----------------+------------------
insert O(1) O(log n) O(log n) O(1) O(1)
accessmin O(n) O(1) O(1) O(1) O(1)
deletemin O(n) O(log n) O(log n) O(log n)* O(log n)
decreasekey O(1) O(log n) O(log n) O(1)* O(1)
delete O(n) O(n) O(log n) O(log n)* O(log n)
merge O(1) O(m log(n+m)) O(m log(n+m)) O(1) O(1)
6) BONUS Heapsort
- in place
- O(n lg n) con cualquiera de estas variantes.
=========================================================
Author: Jérémy Barbay
Date: 2010-10-07 17:36:41 XXX
SCHEDULED: <2010-10-07 Thu 12:00-13:30>
Table of Contents
=================
1 Análisis amortizada
2 Colas de Prioridades
1 Análisis amortizada
~~~~~~~~~~~~~~~~~~~~~~
* Costo Amortizado:
- Se tiene una secuencia de n operaciones con costos
c1,c2,...,cn. Se quiere determinar C=\sum c_i.
- Se puede tomar el peor caso de ci\leq t para tener una
cota superior de C\leq t n.
- Un mejor análisis puede analizar el costo amortizado,
con varias técnicas:
- análisis agragada
- contabilidad de costos
- función potencial.
* Ejemplo simple: Incremento binario
- Incrementar n veces un numero binario de k bits,
- e.g. desde cero hasta 2^k-1, con n=2^k.
- costo \leq k n (brute force)
- costo \leq n + n/2 + ... \leq 2n (costo amortizado)
- La técnica usada aquí es la contabilidad de costos:
- un flip de 0 a 1 cuesta 2
- un flip de 1 a 0 cuesta 0
- cada incremento cuesta 2.
* Función Potencial para contar el costo
- \phi_0 = 0
- \phi_i es el tamaño de la bolsa luego de ejecutar c_1,\ldots,c_i
- \Delta \phi_i = \phi_i - \phi_{i-1}
- costo amortizado = \overline{c_i} = c_i + \Delta\phi_i
- \sum \overline{c_i} = \sum c_i + \phi_n -\phi_0 \geq \sum c_i
- Ejemplo : la analisis del algoritmo para min y max al mismo tiempo.
* En el ejemplo de Incrementacion binaria:
- \phi = cantidad de unos en el numero
- \phi_0 = 0
- c_i = l+1 cuando hay l unos
- \Delta \phi_i = -l+1
- \sum \overline{c_i} = \sum c_i + \phi_n -\phi_0
\geq 2
* Ejemplo: realocación amortizada
- considera el tipo "Vector" en Java.
- de tamaño fijo n
- cuando accede a n+1, crea un otro arreglo de tamaño 2n, y
copia todo.
- cual es el costo amortizado si agregando elementos uno a
uno?
2 Colas de Prioridades
~~~~~~~~~~~~~~~~~~~~~~~
* REFERENCIA: [www.leekillough.com/heaps/]
* Problema: Dado un conjunto (dinámica) de $n$ tareas con
valores, elegir y remudar la tarea de valor máxima.
* operaciones básicas:
- M.build({e1,e2,...,2n})
- M.insert(e)
- M.min
- M.deleteMin
* operaciones adicionales ("Addressable priority queues")
- M.insert(e), volviendo un puntero h ("handle") al elemento insertado
- M.remove(h), remudando el elemento especificado para h
- M.decreaseKey(h,k), reduciendo la llave del elemento especificado para h
- M.merge(Q), agregando el heap Q al heap M.
* Soluciones (conocidas o no):
Linked List Binary Tree (Min-)Heap Fibonacci Heap Brodal Queue [1]
-------------+-------------+---------------+---------------+----------------+------------------
insert O(1) O(log n) O(log n) O(1) O(1)
accessmin O(n) O(1) O(1) O(1) O(1)
deletemin O(n) O(log n) O(log n) O(log n)* O(log n)
decreasekey O(1) O(log n) O(log n) O(1)* O(1)
delete O(n) O(n) O(log n) O(log n)* O(log n)
merge O(1) O(m log(n+m)) O(m log(n+m)) O(1) O(1)
1) Colas de prioridades binarias ("Binary Heaps")
* La solución tradicional
- un arreglo de n elementos
- hijos del nodo i en posiciones 2i y 2i+1
- la valor de cada nodo es mas pequeña que las valores de su hijos.
* Complejidad: Espacio n+O(1), y
Operación Tiempo
-------------------------+----------
M.build({e1,e2,...,2n}) O(n)
M.insert(e) O(\lg n)
M.min O(1)
M.deleteMin O(\lg n)
* Detalles de implementacion (mejorando las constantes)
- Cuidado de no implementar M.build({e1,e2,...,2n}) con n
inserciones (sift up -> O(n\lg n)), pero con n/2
sift-down (-> O(n)).
- En M.deleteMin(), algunas variantes de implementación
(después de cambiar el min con A[n]):
1. dos comparaciones en cada nivel hasta encontrar la
posición final de A[n]
- 2\lg n comparaciones en el peor caso
- \lg n copias
2. una comparación en cada nivel para definir un camino
de tamaño lg n, y una búsqueda binaria para encontrar
la posición final
- \lg n + O(\lg \lg n) comparaciones en el peor caso
- \lg n copias en el peor caso
3. una comparación en cada nivel para definir un camino
de tamaño lg n, y una búsqueda *secuencial* up para encontrar
la posición final
- 2\lg n comparaciones en el peor caso
- \lg n copias en el peor caso
- pero en practica y promedio mucho mejor.
* Flexibilidad de estructuras
+ Porque la complejidad es mejor con un heap que con un
arreglo ordenado?
- Para cada conjunto, hay solamente un arreglo ordenado
que puede representarlo, pero muchos heaps posibles:
eso da mas flexibilidad para la mantención dinámica de
la estructura de datos.
+ Colas de prioridades con punteros ("Addressable priority queues")
- Algún que mas flexible que los arreglos ordenados, las
colas de prioridades binarias todavía son de estructura
muy estricta, por ejemplo para la union de
filas. Estructuras mas flexibles consideran un "bosque"
de arboles. Además, estas estructuras de arboles son
implementadas con puntadores (en ves de implementarlos
en arreglos).
- Hay diferentes variantes. Todas tienen en común los
puntos siguientes:
- un puntero *minPtr* indica el nodo de valor mínima
en el bosque, raíz de alguno arbol.
- *insert* agregas un nuevo arbol al bosque en tiempo O(1)
- *deleteMin* remudas el nodo indicado par minPtr,
dividiendo su arbol en dos nuevos arboles. Buscamos
para el nuevo min y fusionamos algunos arboles (los
detalles diferencian las variantes)
- *decreaseKey(h,k)* es implementado cortando el arbol
al nodo indicado por h, y rebalanceando el arbol
cortado.
- *delete()* es reducido a *decreaseKey(h,0)* y
*deleteMin*
2) "Pairing Heaps"
- Malo rendimiento en el peor caso, pero bastante buena en
practica.
- rebalancea los arboles solamente en deleteMin, y solamente
con pares de raises (i.e. la cantidad de arboles es
reducida por dos a cada deleteMin).
Operación Amortizado
------------------+--------------------------
Insert(C,x) O(1)
Merge O(1)
ExtractMin O(lg n)
decreaseKey(h,k) \Omega(n \lg n \lg\lg n)
3) Colas de prioridades binomiales ("Binomial Heaps")
[en.wikipedia.org/wiki/Binomial_heap]
o p136 de Melhorn y Sanders
* Definición
- Un *arbol binomial* (de orden k) tiene exactamente $k$
hijos de orden distintos k-1,k-2,..., 0. [Un arbol
binomial de orden 0 tiene 0 hijos.]
- Un *bosque binomial* es un conjunto de arboles binomiales
de orden *distintas* (i.e. hay cero o uno arboles de cada
orden).
* Propiedades
- Para cada arbol T
- h(T) \leq lg |T|
- |T| \geq 2^{h(T)}
- Para el bosque
- \forall n hay solamente uno bosque binomial con n nodos.
- al máxima tiene $\lfloor \lg (n+1) \rfloor$ arboles.
- la descomposición del bosque en arboles de orden k
corresponde a la descomposición de n en base de dos.
* Definición
- una *cola binomial* es un bosque binomial donde cada nodo
almacena una clave, y siempre la clave de un padre es
inferior o igual a la clave de un hijo.
* Operaciones
Operación Peor Caso
------------------+-----------
Merge O(lg n)
FindMin O(lg n)
ExtractMin O(lg n)
Insert(C,x) O(lg n)
Heapify O(n)
------------------+-----------
remove(h) O(lg n)
decreaseKey(h,k) O(lg n)
merge(Q) O(lg n)
* Union
- Union de dos arboles binomiales de mismo orden:
- agrega T_2 a T_1 si T_1 tiene la raíz mas pequeña.
- Union de dos bosques binomiales:
- si hay uno arbol de orden k, es lo de la union
- si hay dos arboles de orden k, calcula la union en un arbol de orden k+1
- la propagación es similar a la suma de enteros en binario.
- Complejidad
- O(lg n) en el peor caso
* Insert
- agrega un arbol de orden 0 y hace la union si necesitado
- Complejidad O(log n) en el peor caso
- Puede ser O(1) sin corregir el bosque, que tiene de ser
corregido mas tarde, que puede ser en tiempo O(n) peor
caso, pero sera O(lg n) en tiempo amortizado.
* Mínima
- leí la lista de al máxima $\lfloor \lg (n+1) \rfloor$ raíces
- Complejidad O(lg n)
- Puede ser O(1) si precalculando un puntero al mínima, que
tiene de ser corregido (en tiempo O(\lg n)) a cada modificación.
* DeleteMin
- encontra el min
- remuda el min de su arbol (la raíz)
- reordena su hijos para su orden, en un bosque binomial
- hace la union con el bosque binomial original, menos el arbol del min
- complejidad O(lg n)
* DecreaseKey
- sigue el camino abajo hasta que la condición del heap es
corregida.
- cada arbol tiene altura lg n, entonces la complejidad es
O(lg n) en el peor caso.
* Delete
- reducido a DecreaseKey+DeleteMin
4) Colas de prioridades de Fibonacci ("Fibonacci Heaps")
[en.wikipedia.org/wiki/Fibonacci_heap] o pagina 135 de
Melhorn y Sanders.
* Diferencia con la cola binomial:
- relax la estructura de los arboles (heap-forma), pero de
forma controlada.
- el tamaño de un sub-arbol cual raíz tiene k hijos es al
máxima F_k+2, donde F_k es el k-ésimo numero de
Fibonacci.
* Operaciones
Operación Peor Caso Amortizado
------------------+-----------+------------
Merge O(lg n) O(1)
FindMin O(lg n) O(1)
ExtractMin O(lg n) .
Insert(C,x) O(lg n) O(1)
Heapify O(n) .
------------------+-----------+------------
remove(h) O(lg n) .
decreaseKey(h,k) O(lg n) O(1)
merge(Q) O(lg n) O(1)
5) Overview
(copy de [en.wikipedia.org/wiki/Fibonacci_heap])
Linked List Binary Tree (Min-)Heap Fibonacci Heap Brodal Queue [1]
-------------+-------------+---------------+---------------+----------------+------------------
insert O(1) O(log n) O(log n) O(1) O(1)
accessmin O(n) O(1) O(1) O(1) O(1)
deletemin O(n) O(log n) O(log n) O(log n)* O(log n)
decreasekey O(1) O(log n) O(log n) O(1)* O(1)
delete O(n) O(n) O(log n) O(log n)* O(log n)
merge O(1) O(m log(n+m)) O(m log(n+m)) O(1) O(1)
6) BONUS Heapsort
- in place
- O(n lg n) con cualquiera de estas variantes.
| Compartir | |
|---|---|
| Última Modificación | 7 Oct 201007/10/10 a las 13:38 hrs.2010-10-07 13:38:07 |
| Vistas Únicas | 15 |
