5/23/2018 5 - Divide y Vencers

1/36

Algortmica y Complejidad

Tema 5 Divide y Vencers.

DDDDepartamentoIIIInformticaAAAAplicada

5/23/2018 5 - Divide y Vencers

2/36

Divide y vencers.

1. Mtodo.

2. Un ejemplo sencillo.

3. Complejidad del mtodo.

4. Ejemplo: El mximo subarray.

2

5/23/2018 5 - Divide y Vencers

3/36

Divide y vencers.

1. Mtodo.

2. Un ejemplo sencillo.

3. Complejidad del mtodo.

4. Ejemplo: El mximo subarray.

3

5/23/2018 5 - Divide y Vencers

4/36

Mtodo.

4Divide y vencers.

Dividir.

El problema se divide en varios problemassimilares de menor tamao.

Resolver.

Si los subproblemas son asumibles se resuelven.En caso contrario se vuelve a aplicar el mtodo.

Combinar.

Se combinan las soluciones de los subproblemaspara obtener la solucin total.

Esquema de

tres etapas!

5/23/2018 5 - Divide y Vencers

5/36

5Divide y vencers.

Caractersticas que deben cumplir los problemas para quese pueda aplicar esta tcnica:

El problema se debe poder descomponer en otros

similares pero ms pequeos.

Los nuevos problemas deben ser disjuntos.

Debe ser posible combinar las solucionesindividuales para obtener la global.

Mtodo.

5/23/2018 5 - Divide y Vencers

6/36

6Divide y vencers.

procedure Divide_y_Vencers (P : problema) isbegin

if P es simple thenSolucionar P;

elseDescomponer P en {P1, P2, ..., Pn};

Divide_y_Vencers (P1);

Divide_y_Vencers (P2);. . . . . . . . . . . . . . . . . . .

Divide_y_Vencers (Pn);

Combinar las soluciones de {P1, P2, ..., Pn};end if;

end Divide_y_Vencers;

Mtodo.

5/23/2018 5 - Divide y Vencers

7/36

7Divide y vencers.

Mtodo.

Hasta donde conviene subdividir el problema?

Existir un umbral n0 a partirdel cul es ms rpido aplicar

el algoritmo inmediato.

El clculo de n0 no es trivial y depende de la implementacin.

Es habitual utilizar mtodos empricos para su determinacin.

AlgoritmoImnediato

n0 n

T (n)

Algoritmo

Div. y Venc.

5/23/2018 5 - Divide y Vencers

8/36

Divide y vencers.

1. Mtodo.

2. Un ejemplo sencillo.

3. Complejidad del mtodo.

4. Ejemplo: El mximo subarray.

8

5/23/2018 5 - Divide y Vencers

9/36

Un ejemplo sencillo.

9Divide y vencers.

Problema:

-231

142

313

-34

13n-1

-2n

. . . .A :

function Maximo (i, j : integer) return integer ismax : integer := integer'first;

begin

for k in i .. j loopif A(k) > max then

max := A(k);end if;

end loop;

return max;end Maximo;_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

put ("Valor maximo:"); put (Maximo(A'first, A'last));

La solucin inmediata sera:

Encontrar el valormximo en un arrayde nmeros enteros."

5/23/2018 5 - Divide y Vencers

10/36

Un ejemplo sencillo.

10Divide y vencers.

Enfoque "divide y vencers":

1. Dividir el array en dos partes.

2. Hallar el mximo de cada parte.

3. Seleccionar el mayor de los dos.

Se sigue aplicandode forma recursiva.

5/23/2018 5 - Divide y Vencers

11/36

Un ejemplo sencillo.

11Divide y vencers.

function Maximo (i, j : integer) return integer ismed, max_i, max_d : integer;begin

end Maximo;_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

put ("Valor maximo:"); put (Maximo(A'first, A'last));

5/23/2018 5 - Divide y Vencers

12/36

Un ejemplo sencillo.

12Divide y vencers.

function Maximo (i, j : integer) return integer ismed, max_i, max_d : integer;begin

if i=j thenreturn A(i);

else

end if;

end Maximo;_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

put ("Valor maximo:"); put (Maximo(A'first, A'last));

5/23/2018 5 - Divide y Vencers

13/36

Un ejemplo sencillo.

13Divide y vencers.

function Maximo (i, j : integer) return integer ismed, max_i, max_d : integer;begin

if i=j thenreturn A(i);

elsemed := (i + j) / 2;max_i := Maximo (i, med);max_d := Maximo (med+1, j);

end if;

end Maximo;_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

put ("Valor maximo:"); put (Maximo(A'first, A'last));

5/23/2018 5 - Divide y Vencers

14/36

Un ejemplo sencillo.

14Divide y vencers.

function Maximo (i, j : integer) return integer ismed, max_i, max_d : integer;begin

if i=j thenreturn A(i);

elsemed := (i + j) / 2;max_i := Maximo (i, med);max_d := Maximo (med+1, j);if max_i > max_d then

return max_i;else

return max_d;end if;

end if;

end Maximo;_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

put ("Valor maximo:"); put (Maximo(A'first, A'last));

5/23/2018 5 - Divide y Vencers

15/36

Divide y vencers.

1. Mtodo.

2. Un ejemplo sencillo.

3. Complejidad del mtodo.

4. Ejemplo: El mximo subarray.

15

5/23/2018 5 - Divide y Vencers

16/36

Complejidad del mtodo.

16Divide y vencers.

Problema Problema1

Problema2

Problema

3

Problemaa

Problemaa-1

. . .

T(n/b) + T(n/b ) + T(n/b) + . . . + T(n/b) + T(n/b)

a T ( n / b )

T(n)

Descomposicin del problemay

combinacin de las solucionesO ( n k )

5/23/2018 5 - Divide y Vencers

17/36

Complejidad del mtodo.

17Divide y vencers.

En general responder a esta ecuacin:

a 1, b 2, k 0

T ( n ) = a T ( n / b ) + O ( n k )a : Nmero de subproblemas

en que se descompone.

n/b : Tamao de cada nuevosubproblema.

T ( n ) =

O ( nk ), a < bk

O ( nk log n ), a = bk

O ( n logb a ), a > bk

Cuya solucin es:

5/23/2018 5 - Divide y Vencers

18/36

Complejidad del mtodo.

18Divide y vencers.

function Maximo (i, j : integer) return integer ismed, max_i, max_d : integer;

beginif i=j then

return A(i);else

med := (i + j) / 2;

max_i := Maximo (i, med);max_d := Maximo (med+1, j);if max_i > max_d then

return max_i;else

return max_d;end if;

end if;end Maximo;

O ( 1 )

O ( 1 )

Complejidad del ejemplo sencillo: (Enfoque Divide y Vencers)

5/23/2018 5 - Divide y Vencers

19/36

Complejidad del mtodo.

19Divide y vencers.

function Maximo (i, j : integer) return integer ismed, max_i, max_d : integer;

beginif i=j then

return A(i);else

med := (i + j) / 2;

max_i := Maximo (i, med);max_d := Maximo (med+1, j);if max_i > max_d then

return max_i;else

return max_d;end if;

end if;end Maximo;

T ( n / 2 )T ( n / 2 )

Complejidad del ejemplo sencillo: (Enfoque Divide y Vencers)

5/23/2018 5 - Divide y Vencers

20/36

Complejidad del mtodo.

20Divide y vencers.

T ( n ) = 2 T ( n / 2 ) + O ( 1 )

a = 2b = 2k = 0

a > bk

2 > 20

2 > 1

Complejidad del ejemplo sencillo: (Enfoque Divide y Vencers)

T ( n ) = a T ( n / b ) + O ( n k )

O ( n logb a ) = O ( n log2 2 ) = O ( n )

5/23/2018 5 - Divide y Vencers

21/36

Complejidad del mtodo.

21Divide y vencers.

function Maximo (i, j : integer) return integer ismax : integer := integer'first;

beginfor k in i .. j loopif A(k) > max then

max := A(k);end if;

end loop;return max;

end Maximo;

Complejidad del ejemplo sencillo: (Enfoque Inmediato)

O ( n )

Ambos mtodos tienen la misma complejidad. Divide y Vencers es ms lento por la recursividad.

En este caso es mejor el Enfoque Inmediato.

5/23/2018 5 - Divide y Vencers

22/36

Divide y vencers.

1. Mtodo.

2. Un ejemplo sencillo.

3. Complejidad del mtodo.

4. Ejemplo: El mximo subarray.

22

5/23/2018 5 - Divide y Vencers

23/36

Ejemplo: El mximo subarray.

23Divide y vencers.

"Dados varios nmeros que supondremos almacenados en un array, se tratade encontrar la secuencia de nmeros contiguos cuya suma sea mxima."

Problema:

12

1

2

2

-3

3

-4

4

-9

5

8

6

A : 127

5

8

-6

9

1

10

8

6

12

7

5

8

La solucin sera: cuya suma es 25.

Por ejemplo, dado:

Si existe ms de una solucin, nos conformaremos

con hallar una de ellas.

5/23/2018 5 - Divide y Vencers

24/36

Ej l El i b

5/23/2018 5 - Divide y Vencers

25/36

Ejemplo: El mximo subarray.

25Divide y vencers.

procedure Maximo_Subarray is

. . . . . . . . . . . . . .begin

max := integer'first;for i in A'range loop

suma := 0;for j in i .. A'last loop

suma := suma + A(j);if suma > max then

max := suma;

inf := i;sup := j;

end if;end loop;

end loop;

put ("Indice inferior: "); put (inf); new_line;put ("Indice superior: "); put (sup); new_line;put ("Valor de la suma : "); put (max); new_line;

end Maximo_Subarray;

O ( n2 )

Ej l El i b

5/23/2018 5 - Divide y Vencers

26/36

Ejemplo: El mximo subarray.

Divide y vencers.

Enfoque "divide y vencers":

Se divide el array en dos partes.

3 4 5 6 7 8 9 101 2

Pueden darse tres casos:

3 4 5 6 7 8 9 101 2

El subarray est totalmenteen la parte izquierda.

3 4 5 6 7 8 9 101 2

El subarray est totalmenteen la parte derecha.

3 4 5 6 7 8 9 101 2

El subarrayatraviesa la divisin.

5/23/2018 5 - Divide y Vencers

27/36

Ejemplo: El mximo subarray

5/23/2018 5 - Divide y Vencers

28/36

Ejemplo: El mximo subarray.

Divide y vencers.

procedure Maximo_Subarray (E_inf, E_sup : in natural;S_inf, S_sup : out natural;

S_suma : out integer) is. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

begin

end Maximo_Subarray;_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Maximo_Subarray (A'first, A'last, inf, sup, max);

Ejemplo: El mximo subarray

5/23/2018 5 - Divide y Vencers

29/36

Ejemplo: El mximo subarray.

Divide y vencers.

procedure Maximo_Subarray (E_inf, E_sup : in natural;S_inf, S_sup : out natural;

S_suma : out integer) is. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

begin

if E_inf = E_sup thenS_suma := A(E_inf); S_inf := E_inf; S_sup := S_inf;

else

end if;

end Maximo_Subarray;_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Maximo_Subarray (A'first, A'last, inf, sup, max);

O ( 1 )

Ejemplo: El mximo subarray

5/23/2018 5 - Divide y Vencers

30/36

Ejemplo: El mximo subarray.

Divide y vencers.

procedure Maximo_Subarray (E_inf, E_sup : in natural;S_inf, S_sup : out natural;

S_suma : out integer) is. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

begin

if E_inf = E_sup thenS_suma := A(E_inf); S_inf := E_inf; S_sup := S_inf;

elsemed := (E_inf + E_sup) / 2;Maximo_Subarray (E_inf, med, inf_i, sup_i, max_i);Maximo_Subarray (med + 1, E_sup,inf_d, sup_d, max_d);Subarray_Comun (E_inf, med, E_sup, inf_c, sup_c, max_c);

end if;

end Maximo_Subarray;_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Maximo_Subarray (A'first, A'last, inf, sup, max);

T ( n / 2 )T ( n / 2 )?

O ( 1 )

O ( 1 )

Ejemplo: El mximo subarray

5/23/2018 5 - Divide y Vencers

31/36

Ejemplo: El mximo subarray.

Divide y vencers.

procedure Maximo_Subarray (E_inf, E_sup : in natural;S_inf, S_sup : out natural;

S_suma : out integer) is. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

begin

if E_inf = E_sup thenS_suma := A(E_inf); S_inf := E_inf; S_sup := S_inf;

elsemed := (E_inf + E_sup) / 2;Maximo_Subarray (E_inf, med, inf_i, sup_i, max_i);Maximo_Subarray (med + 1, E_sup,inf_d, sup_d, max_d);Subarray_Comun (E_inf, med, E_sup, inf_c, sup_c, max_c);

if max_i > max_d and max_i > max_c thenS_suma := max_i; S_inf := inf_i; S_sup := sup_i;elsif max_d > max_i and max_d > max_c then

S_suma := max_d; S_inf := inf_d; S_sup := sup_d;else

S_suma := max_c; S_inf := inf_c; S_sup := sup_c;end if;

end if;

end Maximo_Subarray;_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Maximo_Subarray (A'first, A'last, inf, sup, max);

O ( 1 )

T ( n / 2 )T ( n / 2 )?

O ( 1 )

O ( 1 )

Ejemplo: El mximo subarray

5/23/2018 5 - Divide y Vencers

32/36

Ejemplo: El mximo subarray.

Divide y vencers.

procedure Subarray_Comun (E_inf, med, E_sup : in natural;S_inf, S_sup : out natural;

S_suma : out integer) is. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

begin

end Subarray_Comun;

Ejemplo: El mximo subarray

5/23/2018 5 - Divide y Vencers

33/36

Ejemplo: El mximo subarray.

Divide y vencers.

procedure Subarray_Comun (E_inf, med, E_sup : in natural;S_inf, S_sup : out natural;

S_suma : out integer) is. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

begin

suma_izq := integer'first;suma_tmp := 0;for i in reverse E_inf .. med loop

suma_tmp := suma_tmp + A(i);if suma_tmp > suma_izq then

suma_izq := suma_tmp;S_inf := i;

end if;end loop;

end Subarray_Comun;

O ( n )

Ejemplo: El mximo subarray.

5/23/2018 5 - Divide y Vencers

34/36

Ejemplo: El mximo subarray.

Divide y vencers.

procedure Subarray_Comun (E_inf, med, E_sup : in natural;S_inf, S_sup : out natural;

S_suma : out integer) is. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

begin

suma_izq := integer'first;suma_tmp := 0;for i in reverse E_inf .. med loop

suma_tmp := suma_tmp + A(i);if suma_tmp > suma_izq then

suma_izq := suma_tmp;S_inf := i;

end if;end loop;

suma_der := integer'first;suma_tmp := 0;for i in med+1 .. E_sup loop

suma_tmp := suma_tmp + A(i);if suma_tmp > suma_der then

suma_der := suma_tmp;S_sup := i;

end if;end loop;

end Subarray_Comun;

O ( n )

O ( n )

Ejemplo: El mximo subarray.

5/23/2018 5 - Divide y Vencers

35/36

j p y

Divide y vencers.

procedure Subarray_Comun (E_inf, med, E_sup : in natural;S_inf, S_sup : out natural;S_suma : out integer) is

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

begin

suma_izq := integer'first;suma_tmp := 0;for i in reverse E_inf .. med loop

suma_tmp := suma_tmp + A(i);if suma_tmp > suma_izq then

suma_izq := suma_tmp;S_inf := i;

end if;end loop;

suma_der := integer'first;suma_tmp := 0;for i in med+1 .. E_sup loop

suma_tmp := suma_tmp + A(i);if suma_tmp > suma_der then

suma_der := suma_tmp;S_sup := i;

end if;end loop;

S_suma := suma_izq + suma_der;

end Subarray_Comun;

O ( 1 )

O ( n )

O ( n )

Ejemplo: El mximo subarray.

5/23/2018 5 - Divide y Vencers

36/36

j p y

Divide y vencers.

T ( n ) = 2 T ( n / 2 ) + O ( n )

Complejidad del enfoque Divide y Vencers:

a = 2b = 2k = 1

T ( n ) = a T ( n / b ) + O ( n k )

O ( n1 log n ) = O ( n log n )

T ( n ) = O (1) + O (1) + T (n / 2) + T (n / 2) + O ( ? ) + O (1)

O (n) + O (n) + O (1)

n

T (n) n 2

n log n