Complejidad

Programación II17-18 de febrero de 2009

Complejidad

• Complejidad T(n): número de operaciones elementales en función de la medida n

• Hace referencia al caso peor• Notación asintótica: término de T(n) que crece

más rápido en función de nO(logn) logarítmicaO(n) linealO(nlogn) casi-linealO(n2) cuadrática

Funciones iterativas

• Secuencia: la complejidad se suma• Condicional: la complejidad en el caso peor es

el máximo de las dos opciones• Bucles: la complejidad es el producto del

número de iteraciones y la complejidad interior del bucle (incluida la condición)

Funciones recursivas

• Establecer la ecuación de recurrencia:– T(n) en el caso base– T(n) en el caso recursivo

• En el caso recursivo, T(n) depende de T(f(n)) (p.ej. f(n)=n-1, f(n)=n/2)

• Expandir T(f(n)) hasta que la expresión para T(n) sólo depende del caso base

Logaritmos

• log(n) = el exponente a la que 2 se ha de elevar para obtener n

• Ej: log(8) = 3 (porque 23 = 8)• Ej: log(1024) = 10 (porque 210 = 1024)• Aritmética: log(xy) = log(x) + log(y)• Ej: log(1024*1024*1024) = 10+10+10 = 30• Consecuencia: log(n) = número de veces que

se ha de dividir n entre 2 para tener 1

Torres de Hanoi

Torres de Hanoi

Torres de Hanoi

Torres de Hanoi

Torres de Hanoi

accion MoverTorre(n:natural; X,Y,Z:barra)

si (n > 0) entonces

MoverTorre(n-1, X, Z, Y);

MoverDisco(X, Y);

MoverTorre(n-1, Z, Y, X);

fsi

faccion

Torres de Hanoi

• Ecuación de recurrencia:– T(n) = a, n = 0– T(n) = b + 2T(n-1)

Llamadas T(n)1 b + 2T(n-1)2 3b + 4T(n-2)k (2k-1)b + 2kT(n-k)

Torres de Hanoi

• Eliminar la dependencia de T()• k=n T(n-k) = T(0) = a• T(n) = (2k – 1)b + 2ka = (a+b)2k – b• ¿Notación asintótica?

Ejemplo: Mergesort

• Medida: n = D – E• Depende de la complejidad de Combina• Los bucles de Combina se repiten un número

de veces igual al número total de elementos de V1 y V2

• Ecuación de recurrencia:– T(n) = a, n = 0– T(n) = b + cn + 2T(n/2)

Ejemplo: Mergesort

• n/2k = 1 k = log(n)• T(n) = bn + cnlog(n) + an• ¿Notación asintótica?

Llamadas T(n)1 b + cn + 2T(n/2)2 3b + 2cn + 4T(n/4)k (2k-1)b + kcn + 2kT(n/2k)

Ordenación

• Algoritmos de ordenación básicos: O(n2)– Algoritmo de la burbuja (Bubble Sort)– Ordenación por inserción (Insertion Sort)– Ordenación por selección (Selection Sort)

• Mergesort: O(nlogn)• Quicksort???

Ecuaciones de recurrencia

Problema T(n)(caso base)

T(n)(caso recursivo)

O(f(n))

Factorial a b + T(n-1) nBúsquedabinaria

a b + T(n/2) logn

Torres deHanoi

a b + 2T(n-1) 2n

Mergesort a b + cn + 2T(n/2) nlogn

Estudio: Fibonaccifuncion F(n:natural) devuelve naturalsi (n <= 1) entonces

devuelve 1; sino devuelve F(n-2)+F(n-1);

fsiffuncion

Estudio: Fibonacci

• Ecuación de recurrencia:– T(n) = a, n <= 1– T(n) = b + T(n-1) + T(n-2), n > 1

Llam. T(n)1 b + T(n-1) + T(n-2)2 2b + 2T(n-2) + T(n-3)3 4b + 3T(n-3) + 2T(n-4)4 7b + 5T(n-4) + 3T(n-5)k (F(k+1)-1)b + F(k)T(n-k) + F(k-1)T(n-k-1)

Estudio: Fibonacci

• k = n-1T(n-k) = T(1) = T(n-k-1) = T(0) = a• T(n) = (F(n)-1)b + F(n-1)T(1) + F(n-2)T(0)• Notación asintótica: T(n) = ¡O(F(n))!• Aproximación: O(F(n)) = O(1,6n)• ¡Complejidad exponencial!

Estudio: Fibonacci

• Versión iterativafuncion F(n:natural) devuelve natural

variable f1,f2,tmp:natural;f1 := f2 := 1;mientras (n > 1) hacer

tmp := f2;f2 := f1 + f2;f1 := tmp;n := n – 1;

fmientrasdevuelve f2;

ffuncion

Estudio: Fibonacci

• ¿Complejidad versión iterativa?

Estudio: Fibonacci

• La actualización de F(i),F(i+1) se puede ver como la multiplicación con una matriz

=

• Por lo tanto, obtenemos

= =

0 1

1 1

F(i)

F(i+1)

F(i-1)

F(i)

F(n)

F(n+1)

0 1

1 1

F(0)

F(1)

n 0 1

1 1

n 1

1

Estudio: Fibonacci

• Podemos calcular el exponente de la matriz de manera recursiva

=

= n par

= n impar

1 0

0 1

0 1

1 1

0 1

1 1

0 1

1 1

0 1

1 1

0 1

1 1

n2

0 1

1 1

n2

0 1

1 1

0

n

n 0 1

1 1

n2

n2

Estudio: Fibonaccifuncion Exp(n:natural) devuelve matriz de natural

variable A,B:matriz (2x2) de natural;

si (n = 0) entonces

devuelve [[1,0],[0,1]];

sino

A := Exp(n div 2);

B := A * A; // multiplicacion de matrices 2x2

si (n mod 2 > 0) entonces

B := B * [[0,1],[1,1]];

fsi

devuelve B;

fsi

ffuncion

Estudio: Fibonacci

funcion F(n:natural) devuelve natural

variable A:matriz (2x2) de natural;

A := Exp(n);

devuelve A(1,1) + A(1,2);

ffuncion

Estudio: Fibonacci

• ¿Complejidad Exp(n)?• ¿Complejidad F(n)?

Estudio: Fibonacci

• Fibonacci recursivo original: O(1,6n)• Fibonacci iterativo: O(n)• Fibonacci recursivo c/ exponente: O(logn)

n=10 n=100 n=1000

O(1,6n) 110 2,6*1020 1,3*10204

O(n) 10 100 1000

O(logn) 3 7 10