Divide Y Venceras

Algoritmos de tipo Divide y Vencerás

Algoritmos de tipo Divide y Vencerás
Ideas generales Esquema de resolución Complejidad temporal El problema del balanceo: quicksort revisited Ejemplos • Torres de Hanoi • Búsqueda dicotómica • Ordenación por mezcla • Exponenciación Ejercicios

L.J. Rodríguez

Algoritmos y Estructuras de Datos

Página 1

Algoritmos de tipo Divide y VencerásIdeas generales
Tamaño del problema original: n Se descompone en L sub-problemas más pequeños Tamaño del sub-problema i: mi < n de modo L que i=1 mi = n Hipótesis: resolver un problema de tamaño más pequeño tiene un coste menor y la solución para los casos muy pequeños (n ≤ n0 ) es trivial Se resuelven los L sub-problemas por separado Se combinan las L soluciones para obtener la solución al problemaoriginal

L.J. Rodríguez

Algoritmos y Estructuras de Datos

Página 2

Algoritmos de tipo Divide y Vencerás

subproblema 1 tamaño: m1

solución 1

problema original tamaño: n

subproblema 2 tamaño: m2

solución 2 solución general ..............

..............

dividir
subproblema L tamaño: mL solución L

combinar

resolver
L.J. Rodríguez

Algoritmos y Estructuras deDatos

Página 3

Algoritmos de tipo Divide y Vencerás
función dyv (p: PROBLEMA): SOLUCIÓN var i: entero C: array[1..MAX] de PROBLEMA D: array[1..MAX] de SOLUCIÓN fin_var usa función tamaño (s: PROBLEMA): entero función trivial (s: PROBLEMA): SOLUCIÓN procedimiento dividir (s: PROBLEMA, ref A: array[1..MAX] de PROBLEMA, k: entero) función combinar (B: array[1..MAX] de SOLUCIÓN, k: entero):SOLUCIÓN fin_usa principio si tamaño(p) ≤ n0 entonces devolver trivial(p) si_no dividir(p,C,L) paratodo i ∈ [1..L] hacer D[i] ← dyv(C[i]) fin_paratodo devolver combinar(D,L) fin_si fin /* dyv */
L.J. Rodríguez

Algoritmos y Estructuras de Datos

Página 4

Algoritmos de tipo Divide y Vencerás

Complejidad temporal
  Ttrivial (n) + c1  
n ≤ n0
L i=1

Tdyv (n) =

   Tdividir(n, L) +

Tdyv (mi ) + Tcombinar (n, L) + c2

n > n0

L.J. Rodríguez

Algoritmos y Estructuras de Datos

Página 5

Algoritmos de tipo Divide y Vencerás

Complejidad temporal: caso particular
El problema original –de tamaño n– se divide en L subproblemas de tamaño n/b, con L ≥ 1 y b ≥ 2 Ttrivial (n) ∈ Θ(1) (n0 ≥ 1) Tdividir (n, L) + Tcombinar (n, L) ∈ Θ(nk ), con k ≥ 0   1        
LTdyv
n b

n ≤ n0

Tdyv (n) =

+ nk

n > n0

L.J. Rodríguez

Algoritmos y Estructuras de Datos

Página 6

Algoritmos de tipo Divide y Vencerás

T (n) = LT (n/b) + nk para n > n0 T (n) = 1 para n ≤ n0 Vamos a resolver la recurrencia para n ∈ {bn0 , b2 n0 , b3 n0 , . . .} Hipótesis: T (n) continua y monótona no decreciente Cambio de variable: n ≡ bi n0 ⇔ i ≡ logb (n/n0) Nos queda la siguiente expresión: t(i) ≡ T (bi n0 ) = LT (bi−1 n0 ) + bi n0 ≡ Lt(i − 1) + nk bik 0 Y la recurrencia queda: t(i) − Lt(i − 1) = nk 0 b
k i k

La solución general es:   c Li + c b k i 1 2 t(i) =  c1 b k i + c 2 i b k
L.J. Rodríguez

L = bk
i

L = bk
Página 7

Algoritmos y Estructuras de Datos

Algoritmos de tipo Divide y Vencerás

L = bk
Invirtiendo el cambionos queda: T (n) = = donde: C1 C2 = c1 /n0
logb L logb L k

c1

n n0

+ c2

n n0

C1 nlogb L + C2 nk

= c2 /nk 0

Sustituyendo en la recurrencia original se obtiene: nk = = T (n) − LT (n/b) C1 nlogb L + C2 nk n n logb L −L C1 + C2 b b L 1− k b C 2 nk
L −1 bk k

=

Y de ahí: C2 = 1 −
L.J. Rodríguez

Algoritmos y Estructuras de Datos

Página 8

Algoritmos de tipo Divide yVencerás

L = bk
Se pueden sacar conclusiones sobre el orden de magnitud de T (n) independientemente del valor de C1 La solución general es: L logb L T (n) = C1 n + 1− k b L < bk • 1−
L −1 bk −1

nk

> 0 y k > logb L

• Por tanto: T (n) ∈ Θ(nk ) n ∈ {bn0 , b2 n0 , b3 n0 , . . .} • T (n) continua y monótona no decreciente =⇒ L > bk • 1−
L −1 bk

∀n T (n) ∈ Θ(nk )

< 0 y k < logb L T...