complejidad - uc3m · volver de un método etc. cdk@it.uc3m.es java: complejidad / 5 ejemplo (en...

1

Complejidad

Carlos Delgado Kloos Ingeniería Telemática Univ. Carlos III de Madrid

cdk@it.uc3m.es Java: Complejidad / 1

Comparación

  long fib (int n) {if (n<=1) return n; else return fib(n-1)+fib(n-2); }

  long fibo (int n,x,y) {if (n<=1) return x+y; else return fibo(n-1,y,x+y); }

cdk@it.uc3m.es Java: Complejidad / 2

  Los dos métodos calculan la función fib correctamente, ¿pero cuál preferiría?   El primero es más claro.   El segundo es más eficiente.

2

¿Cómo medimos?

  Midiendo el tiempo de ejecución (en función del tamaño de la entrada)  No podemos probar con todas las entradas  Es necesario implementar el algoritmo  Depende del software y el hardware

  Busquemos otra medida  Más abstracta  Más fácil de obtener

cdk@it.uc3m.es Java: Complejidad / 3

¿Cómo medimos?

  Asociamos a cada algoritmo: f(n)   Emplearemos el caso peor para

caracterizar el tiempo de ejecución   Es más fácil de calcular   Interesa la velocidad de crecimiento del

tiempo de ejecución en función del tamaño de la entrada

  Comportamiento asintótico

cdk@it.uc3m.es Java: Complejidad / 4

Tamaño de la entrada

3

¿Cómo medimos?

  Asociamos a cada operación primitiva un tiempo de ejecución constante:  Asignación  Llamada a método  Operación aritmética, etc.  Indexación en array  Seguir una referencia  Volver de un método  Etc.

cdk@it.uc3m.es Java: Complejidad / 5

Ejemplo (en pseudocódigo)

  Hallar el máximo de un array   Entrada: un array A con n enteros   Salida: el elemento mayor de A   Algoritmo: arrayMax(A,n)   current=A[0] for i=1 to n-1 do if current<A[i] then current=A[i]

return current

cdk@it.uc3m.es Java: Complejidad / 6

4

Ejemplo (en pseudocódigo)

  current=A[0] for i=1 to n-1 do if current<A[i] then current=A[i]

return current   Mínimo núm. de operaciones (si es A[0]):

2+1+n+4(n-1)+1=5n   Máximo núm. de operaciones (si A creciente):

2+1+n+6(n-1)+1=7n-3

cdk@it.uc3m.es Java: Complejidad / 7

Notación O

cdk@it.uc3m.es Java: Complejidad / 8

n0

f(n)

c⋅g(n)

f(n) es O(g(n)) sii f(n) ≤ c ⋅ g(n) para n ≥ n0

5

Notación O

  7n-3 es O(n)  c=7, n0=1  7n-3 ≤ 7n

  20n3+10n log n+5 es O(n3)   3 log n + log log n es O(log n)   2100 es O(1)   5/n es O(1/n)

cdk@it.uc3m.es Java: Complejidad / 9

Crecimiento de funciones

log n √n n n log n n2 n3 2n

1 1,4 2 2 4 8 4

2 2,0 4 8 16 64 16

3 2,8 8 24 64 512 256

4 4,0 16 64 256 4.096 65.536

5 5,7 32 160 1.024 32.768 4.294.967.296

6 8,0 64 384 4.096 262.144 1,8 * 1019

7 11,0 128 896 16.536 2.097.152 3,4 * 1038

cdk@it.uc3m.es Java: Complejidad / 10

6

Crecimiento de funciones

cdk@it.uc3m.es Java: Complejidad / 11

Tamaño máximo de un problema

Tiempo de ejecución

1 segundo 1 minuto 1 hora

400n 2.500 150.000 9.000.000

20nlog n 4.096 166.666 7.826.087

2n2 707 5.477 42.426

n4 31 88 244

2n 19 25 31

cdk@it.uc3m.es Java: Complejidad / 12

7

Ejemplo

  Dado un array A de n números   Calcular otro array B, tal que:

∑ij=0A[j]

B[i]=————— i+1

cdk@it.uc3m.es Java: Complejidad / 13

Solución 1

  for i=0 to n-1 do a=0 for j=0 to i do a=a+A[j] B[i]=a/(i+1)

return B

cdk@it.uc3m.es Java: Complejidad / 14

8

Solución 1: Análisis

  Partes:  Inicializar y devolver array B: O(n)  Bucle i: se ejecuta n veces  Bucle j: se ejecuta 1+2+3+...+n=n(n+1)/2

veces: O(n2)

  Total:  O(n)+O(n)+O(n2)= O(n2)  Orden cuadrático

cdk@it.uc3m.es Java: Complejidad / 15

Optimización

  B[i]=(A[0]+...+A[i])/(i+1)   B[i+1]=(A[0]+...+A[i]+A[i+1])/(i+2)

  B[i+1]=(B[i]*(i+1)+A[i+1])/(i+2)

cdk@it.uc3m.es Java: Complejidad / 16

9

Solución 2

  s=0 for i=0 to (n-1) do s=s+A[i] B[i]=s/(i+1)

return B

cdk@it.uc3m.es Java: Complejidad / 17

Solución 2: Análisis

  Partes:  Inicializar y devolver array B: O(n)  Inicializar s: O(1)  Bucle i: se ejecuta n veces

  Total:  O(n)+O(1)+O(n)=O(n)  Orden lineal

cdk@it.uc3m.es Java: Complejidad / 18

10

¿Hay un algoritmo para resolver cualquier problema?

  ¿Se puede resolver cualquier problema por medio de un algoritmo?

  ¿Cuál es el límite de la computabilidad?   Hilbert pensaba que todos los problemas

matemáticos eran computables   En los años 1930, Gödel, Turing, Church y

otros demostraron que no es así

cdk@it.uc3m.es Java: Complejidad / 19

Computabilidad

  Un problema matemático se llama computable, si puede puede ser resuelto en principio por un dispositivo de computación

  Hay una clasificación de problemas matemáticos en computables y no computables

cdk@it.uc3m.es Java: Complejidad / 20

11

Dispositivo de computación

  ¿Cuál es el dispositivo de computación más sencillo, pero que sin embargo entraña la capacidad de todos los ordenadores?

  Se definieron varios dispositivos (imaginarios) o formalismos matemáticos

cdk@it.uc3m.es Java: Complejidad / 21

Definiciones de computabilidad

  Andrey Markov (1856-1922)  Algoritmos de Markov

  Alonzo Church (1903-95)  Cálculoλ

  Kurt Gödel (1906-78)  Funciones recursivas

  Stephen Kleene (1909-94)  Sistemas formales

  Alan Turing (1912-54)  Máquinas de Turing

cdk@it.uc3m.es Java: Complejidad / 22

12

Máquina de Turing

  Componentes:  Control con un nº finito de estados  Cabeza lectora/escritora  Cinta infinita

  Funcionamiento:  Cabeza lee símbolo de cinta y

en función de él y del estado,  escribe un símbolo en la cinta,

la mueve y pasa a un nuevo estado

cdk@it.uc3m.es Java: Complejidad / 23

Máquinas de Turing

  MT determinista, si para cada combinación (símbolo leído, estado), hay una única continuación (símbolo a escribir, estado, movimiento)

  MT no-determinista si hay más

cdk@it.uc3m.es Java: Complejidad / 24

13

Clases de problemas

  El conjunto de problemas computables se dividen en varias clases:  P (polinomial con MT

determinista)  NP (polinomial con MT

no-determinista)  etc.

cdk@it.uc3m.es Java: Complejidad / 25

¿Es P = NP?

  “Resolver un sudoku” (NP) vs “Comprobar si está bien resuelto” (P)

  El Clay Mathematics Institute ofrece US$ 1 millón para el que resuelva si los dos conjuntos son iguales o no  www.claymath.org/millennium

cdk@it.uc3m.es Java: Complejidad / 26