Tema 2 eficiencia y complejidad
-
Upload
carlos-a-iglesias -
Category
Technology
-
view
652 -
download
1
description
Transcript of Tema 2 eficiencia y complejidad
Análisis y Diseño de Software
Departamento de Ingeniería de Sistemas Telemáticoshttp://moodle.dit.upm.es
Tema 2a. Eficiencia y Complejidad
Carlos A. Iglesias <[email protected]>
Eficiencia y Complejidad 2
Teoría
Ejercicio práctico en el ordenador / Problema
Ampliación de conocimientos
Lectura / Vídeo / Podcast
Práctica libre / Experimentación
Leyenda
Eficiencia y Complejidad 3
Bibliografía
● Eficiencia algorítmica– http://en.wikipedia.org/wiki/Algorithmic_efficien
cy – http://en.wikipedia.org/wiki/Analysis_of_algorith
ms#Shortcomings_of_empirical_metrics● http://jungla.dit.upm.es/~pepe/doc/adsw/Complejidad.pdf
Eficiencia y Complejidad 4
Temario
● Complejidad: el problema
● Espacio de problemas
● Notación O (Big O)
● Evaluar la complejidad de un algoritmo
● Análisis y conclusiones
Eficiencia y Complejidad 5
Objetivos
● Entender cómo se pueden comparar algoritmos
● Entender qué es una medida de complejidad
● Conocer la notación O● Conocer la notación O para algoritmos
básicos de ordenación y búsqueda● Saber razonar con la notación O
Eficiencia y Complejidad 6
El problema
● ¿En qué nos basamos para seleccionar un algoritmo cuando hay tantos disponibles (y tan parecidos)?
Eficiencia y Complejidad 7
● “En casi todos los cálculos, es posible una gran variedad en la forma de de llevar a cabo los procesos de computación. […] Es esencial seleccionar la forma que reduzca al mínimo el tiempo para completar un cálculo”
Ada Lovelace
¿Qué elegir?
Eficiencia y Complejidad 8
¿Qué elegir?
● El algoritmo más eficiente
● Eficiencia: inversamente proporcional a los recursos (memoria, tiempo, …) consumidos por un algoritmo
Eficiencia y Complejidad 9
Formas de seleccionar
● De forma 'empírica':– Medimos su recursos consumidos de los
algoritmos (tiempo, memoria, uso de comunicaciones, disco, consumo energético, …, caso mejor, peor, medio, …)
● De forma 'analítica' / teórica:– Calculamos un 'límite' de estos recursos,
analizando el algoritmo y su implementación
Eficiencia y Complejidad 10
Medidas empíricas
● Medimos (p.ej. Tiempo).
// Creo el entornoAlgoritmo a = new Algoritmo();Datos d = new Datos(); // relleno
// Midolong t1 = System.nanoTime();a.run(d);long t2 = System.nanoTime();long duracion = t2 – t1;
Eficiencia y Complejidad 11
Medidas empíricas● Como los algoritmos son genéricos, las medidas empíricas pueden
verse afectadas por:– El lenguaje de programación– El entorno de ejecución / sistema operativo (p.ej. JVM GC, multinúcleo, …)– Los datos que usemos al medir
● Pueden ayudarnos a entender cómo funcionan, y tenemos que analizar bien el experimento cuando obtenemos resultados inesperados
● Si medimos, podemos intentar ajustar las gráficas, y ver qué distribución siguen (polinómico, lineal, etc.). Si estás interesado, mira los apuntes.
Eficiencia y Complejidad 12
Medidas teóricas: notación O (Big O Notation)
● Nos ayuda a clasificar algoritmos según cómo crezca su respuesta (tiempo de ejecución, memoria, etc.) con el número de datos de entrada
● Algoritmos con la misma “respuesta”, tendrán la misma notación O
● Representa la cota del valor peor que pueden tomar, el límite superior
Eficiencia y Complejidad 13
Orden de complejidad
● f(n) = O(g(n)) significa que C*g(n) es un límite superior de f(n) para un n
o y C
positivos
∣ f (n)∣≤C∣g (n)∣,∀ n>n0Ej.3n2−100n+6=O (n2) , porque3n2>3n2−100n+6cuando n>0Ej.3n2−100n+6=O (n3) , porque n3>3n2−100n+6 cuando n>3Ej.3n2−100n+6≠O (n) , porque paratodo c que escojo cn<3n2
cuando n>c
Eficiencia y Complejidad 14
Orden de complejidad
●Realmente cuando decimos n2=O(n3) lo que estamos diciendo es que – O(n3) es un conjunto de funciones– f(n) = n2 es una de las funciones que pertenecen a
esta clase de funciones de complejidad O(n3)
●Otra forma de verlo es decir que f(n) = O(g(n)) se lee como 'g domina a f':
● Nos basta una función de referencia por clase
g≫n
Eficiencia y Complejidad 15
Funciones de Referencia
Función Nombre
g(n) = 1 Constante
g(n) = log(n) Logarítmico
g(n) = n Lineal
g(n) = n *log(n) Lineal logarítmico
g(n) = n2 Cuadrático
g(n) = nc Potencial
g(n) = cn, n >1 Exponencial
g(n) = n! Factorial
n!≫cn≫n2≫nc≫nlogn≫n≫logn≫1
Eficiencia y Complejidad 16
Propiedades O(n)
●Adición
– Ej. n3+n2+n+1 = O(n3), importa el término mayor si n → ∞
● Factor multiplicador
– Puedo multiplicar por 1/c al hacer el análisis
O(g (n))+O( f (n))→O (max ( f (n) , g (n)))
O(cf (n))→O ( f (n))
Eficiencia y Complejidad 17
Definición alternativa
● Otra forma de definir que g>>n
●El conjunto incluye las funciones f(n) que son menos complejas que g(n) y las que son igual de complejas que g(n)
∣ f (n)∣≤C∣g (n)∣,∀ n>n0
f (n)=O(g (n))={ f (n) , limn→∞
f (n)g (n)
<∞}
Eficiencia y Complejidad 18
Comparando funciones
limn→∞
f (n)g (n)
=0 si f (n)es menos compleja que g (n)
limn→∞
f (n)g (n)
=∞ si f (n)es más compleja que g (n)
limn→∞
f (n)g (n)
=k si f (n)tienemisma complejidad que g (n)
Eficiencia y Complejidad 19
Órdenes de funciones comunes
Notación Nombre Comentario
O(1) Constante Ideal
O(log n) Logarítmico Muy bueno
O(n) Lineal normal
O(nlogn) Lineal logarítmico
razonable
O(n2) Cuadrático tratable
O(nc) Potencial “tratable”
O(cn), n >1 Exponencial No es práctico
O(n!) Factorial inviable
Eficiencia y Complejidad 20
Orden
Eficiencia y Complejidad 21
O(1): complejidad constante
● Complejidad constante, independiente del tamaño de la entrada
boolean isElementoNulo(Object [] array, int indice) { if (a[indice] == null) {
return true; } return false;}
boolean isElementoNulo(Object [] array, int indice) { return (a[indice] == null);}
Eficiencia y Complejidad 22
O(logn) - Logarítmico
● logb(Y): Número de veces que Y se puede dividir
por b hasta que vale 1. Inverso de la exponencial.● Ej. 24 = 2 * 2 * 2 * 2 = 16
● log2(16) : 16/2=8; 8/2=4;
4/2=2; 2/2=1--> 4 veces--> log2(16)= 4
● Como log(nc) = c * log(n) ambos tienen la misma notación O, no nos importa el exponente de n.
●Lo mismo con la base, como logc(b) =
logc(a)*log
a(b), no importa la base
Eficiencia y Complejidad 23
O(logn)
●Ej. búsqueda binaria. Buscamos un número en el listín telefónico ordenado alfabéticamente. Dividimos entre dos el listín y vamos a la mitad donde está si no está, dividimos otra vez.
● El caso peor es el número de veces que dividimos n por 2 → log
2(n) → O(logn)
Eficiencia y Complejidad 24
O(n): lineal
● Consumo de recursos directamente proporcional a la entrada
● Ej. búsqueda lineal. Caso peor: buscamos el último elemento, recorremos n → O(n)
Eficiencia y Complejidad 25
O(nc): polinómico
●Ahora el orden sí es importante●Normalmente se da si hacemos un cálculo
con un elemento y con el resto de elementos
● Ej. Ordenar método de laburbuja O(n2).
●Comparaciones:(N – 1) + (N – 2) + … + 1 = N * (N-1)/2 → O(N2)
Eficiencia y Complejidad 26
O(cn): exponencial
●También es relevante el exponente
Eficiencia y Complejidad 27
¿Cómo calculamos la complejidad? (I)
●Analizamos el código● En sentencias condicionales (if/else-switch),
cogemos la rama 'peor'●Bucles:
– Si el bucle no depende de n, simplemente es una cte O(1), que quitamos
– Si el bucle depende de n, tendremos O(n)– Si tenemos bucles anidados, que dependen de n, si
son dos, tenemos O(n2) (nos sale 1 + 2 + .. = n(n-1)/2)
Eficiencia y Complejidad 28
¿Complejidad?
Eficiencia y Complejidad 29
¿Cómo calculamos la complejidad? (II)
●Si el bucle es multiplicativo, es decir, no es lineal con n:
int c = 1;while (c < n) {
sentencias O(1);c *= 2;
}
Para n = 10:c= 1, c = 2, c = 4, c= 8En general, vale 2k <= n→ k = log
2(n) → log(n)
int c = n;while (c > 1) {
sentencias O(1);c /= 2;
}
Para n = 10:c= 10, c = 5, c = 2, c= 1 → log(n)
Eficiencia y Complejidad 30
¿Cómo calculamos la complejidad? (II)
●Si combinamos, nos sale O(nlogn):for (int i = 0; i < n; i++) { int c = i; while (c > 0) {
sentencias O(1);c /= 2;
}}
Eficiencia y Complejidad 31
Ejemplo. Calcular complejidad (I)
Eficiencia y Complejidad 32
Ejemplo (II)
Se ejecuta n (= coef.length) veces (0 a n - 1)
Eficiencia y Complejidad 33
Ejemplo (III)
Para cada i, se ejecuta i – 1 vecesEs decir, 0 + 1 + 2 + … + n – 2 = (n – 2 + 1) / 2 = (n – 1) / 2
Eficiencia y Complejidad 34
Ejemplo (IV)
En total, se ejecuta n * (n – 1) / 2 → O(n2)
Eficiencia y Complejidad 35
Optimizamos
Eficiencia y Complejidad 36
Complejidad potencia (I)
●Si siempre tomara la rama impar, se ejecutaría y -1, y – 2, … 0 → O(n)
● Si siempre fuera la impar, y2/4, y4/16, …yk/2k→ O(logn)
Eficiencia y Complejidad 37
Complejidad potencia (II)
● Como vamos restando uno, una vez irá a una rama y otra vez a la otra rama
● Ej. x^31: 31, 30, 15, 14, 7, 6, 3, 2, 1
● Caso peor: que empiece con un impar
● Como vamos dividiendo por 2 en la parte impar, tendremos log
2(y) términos y otro
tanto de términos impares. En total: 2*log2(y)
● → Potencia tiene complejidad O(logn)
Eficiencia y Complejidad 38
Complejidad evaluaPolinomio2
● Tenemos un bucle que sucede n veces, donde se llama a potencia → O(nlogn)
Eficiencia y Complejidad 39
Complejidad evaluaPolinomio3
● Almacenamos las potencias
● Ahora el bucle se ejecuta n veces → O(n)
Eficiencia y Complejidad 40
Complejidad evaluaPolinomio4
●Misma complejidad que antes, O(n)
● Sin embargo, sólo ejecuta N sumas y multiplicaciones (el anterior 2N multiplicaciones y N sumas, tarda el doble pero misma complejidad)
Eficiencia y Complejidad 41
Medimos tiempos
● Para N: 10, 100, 500, 1000
● Calculamos coeficientes aleatorios y ejecutamos 10.000 veces
Eficiencia y Complejidad 42
Medimos tiempos
N EvaluaPolinomio1 EvaluaPolinomio2 EvaluaPolinomio3 EvaluaPolinomio4
10 18 24 13 17
50 68 82 28 28
100 231 240 42 45
500 3901 1375 68 72
1000 18546 3981 107 108
Eficiencia y Complejidad 43
Fibonacci1 – recursivo
● fib(n) es función de fib(n-1)+fib(n-2)● Muy difícil calcular la complejidad
Eficiencia y Complejidad 44
Fibonacci1 - Truco
● Sea T(n) el tiempo de ejecución
● Si suponemos que T(n) es exponencial:
T (n)=T (n−1)+T (n−2)T (n)=an
an=an−1+an−2
a2=a+1
a=1+ √52
≃1.618
fib(n)≃1.6n
O ( fib (n))∈O(1.6n)
Eficiencia y Complejidad 45
Fibonacci1
● Si E(n) es el Espacio en Memoria ocupado, ¿cuál es su complejidad?
fib(n)
fib(n-1) fib(n-2)
fib(n-2) fib(n-3)
fib(0)
...
...
...
E (n)∈O (n)( pila de llamadas)
Eficiencia y Complejidad 46
Comprobamos
● Se cumple el límite limn→∞
f (n)g (n)
=k
Eficiencia y Complejidad 47
Fibonacci-2 iterativo
● Tenemos un bucle que se ejecuta n-3 veces, con que...
T (n)∈O(n)E (n)∈O (1)
Eficiencia y Complejidad 48
Fibonacci-3 con memoria
● ¿Complejidad? Si nos fijamos, cómo vamos guardando valores, sólo calculamos 1 vez cada valor, con que es O(n)
T (n)∈O(n)E (n)∈O (n)(datos)
Eficiencia y Complejidad 49
Fibonacci3 recursivo con memoria
fib(n)
fib(n-1) fib(n-2)
fib(n-2) fib(n-3)
fib(2)
...
fib(1) fib(0)
T (n)∈O(n)E (n)∈O (n)(datos)
Eficiencia y Complejidad 50
Memoria vs tiempo
● En este caso 'gastamos más memoria': E(n) → O(n) datos memorizados para ahorrar tiempo (y no recalcular valores)
● Es una técnica habitual para optimizar (caché)
Eficiencia y Complejidad 51
Variante: Recursivo con memoria limitada
●Limitamos el buffer a los n más usados (de 0 a n - 1
Complejidad Tiempo de ejecución difícil de calcular, depende de cómo de grande sea n
Eficiencia y Complejidad 52
Fibonacci4 – fórmula de Binet
● No depende de n → T(n), E(n) → O(1)
Binet (1786- 1856)
Eficiencia y Complejidad 53
Tiempos
Eficiencia y Complejidad 54
Tipos de problemas
● Hay muchos problemas que no sabemos un algoritmo para resolverlos.
● Entre los que sabemos resolver, los tipos más importantes son:– Problemas P: Problemas con complejidad
polinómica (O(n), O(n2), etc.)– Problemas NP: Problemas que no pueden
resolverse en un tiempo polinómico, e intentamos buscar otro algoritmo.
Eficiencia y Complejidad 55
Comprobación empírica
● Una vez que tomamos las medidas, podemos intentar ver se ajustan a una complejidad conocida
●Hacemos un cambio de variable en el eje X y vemos si nos sale una recta
Eficiencia y Complejidad 56
Ejemplo
Eficiencia y Complejidad 57
Cambio x=n2
Eficiencia y Complejidad 58
Cambio x=nlog(n)
Eficiencia y Complejidad 59
Resumen
● Para elegir un algoritmo, podemos– Seguir un enfoque analítico y corroborar
empíricamente– Seguir un enfoque empírico
● La notación O nos facilita razonar sobre la eficiencia de un algoritmo
Eficiencia y Complejidad 60
Notación O
Eficiencia y Complejidad 61
Preguntas● Si pruebo dos algoritmos en mi ordenador, y uno tarda
10 segundos y otro 20 segundos, ¿cuál es más eficiente?
● Si sé que un algoritmo tiene una respuesta 9n3 + 2n2 + 4n +2, ¿cuál sería su notación O?
● ¿Qué significa que O es el límite asintótico?
● Si tienes unos algoritmos A, B, C con complejidad O(n), O(nlogn) y O(n2), ¿en qué orden los escogerías?
● Para cualquier valor de n, será siempre más rápido un algoritmo O(n)) que uno con O(n2)