complejidad - uc3m · volver de un método etc. [email protected] java: complejidad / 5 ejemplo (en...

1

Complejidad

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

[email protected] 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); }


  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


¿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


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.


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


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


Notación O


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)


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


6

Crecimiento de funciones


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


7

Ejemplo

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

∑ij=0A[j]

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


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


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


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)


9

Solución 2

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

return B


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


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í


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


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


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


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


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


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.


¿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


complejidad - uc3m · volver de un método etc. [email protected] java: complejidad / 5 ejemplo (en...

Documents