Complejidad
Programación II
10-11 de febrero de 2009
Eficiencia de algoritmos
• ¿Cómo determinar si un algoritmo es mejor
que otro?
– Fácil a implementar
– Fácil a entender
– Fácil a modificar
– Usa menos memoria
– Menor tiempo de ejecución
Tiempo de ejecución
• El tiempo de ejecución de un programa
depende de varios factores:
– Los datos de entrada
– La calidad del código generado por el compilador
– La máquina donde se ejecuta el programa
– La complejidad del algoritmo en que se basa
Complejidad
• Complejidad: número de operaciones
elementales en función de la entrada
• Si n es la medida de los datos de entrada, T(n)
denota el tiempo de ejecución
• T(n) no tiene unidad
• Hace referencia al caso peor (otras opciones:
caso promedio, caso mejor)
Operaciones elementales
• Operaciones aritméticas (adición, sustracción,
multiplicación, división, módulo)
• Asignación de valores a una variable
• Comparaciones
• Devolución del resultado
Composición de la complejidad
• 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)
Ejemplo: Factorial
• Calcular T(n) para la versión iterativa de
Factorial(n)
funcion Factorial(n:natural) devuelve natural
resultado := 1;
mientras (n > 0) hacer
resultado := resultado * n;
n := n – 1;
fmientras
devuelve resultado;
ffuncion
Notación asintótica
• Mide la velocidad de crecimiento de una
función
• Una función T(n) es O(f(n)) (O-grande de f(n))
si T(n) crece como f(n)
• Por ejemplo, la función T(n) = 5n + 3 es O(n),
es decir, crece como n
• En general, es igual al término más grande
(constantes excluidos)
Definición matemática
O(f(n)) = {T(n) : c,N, n>N, T(n) < c*f(n)}
c*f(n)
T(n)
f(n)
N
n
Funciones típicas
Velocidad de crecimiento
Nombre de la función
O(1)
constante
O(log(n))
logarítmica
O(n)
lineal
O(nlog(n))
casi lineal
O(n2)
cuadrática
O(nk)
polinómica
O(2n)
exponencial
Velocidad de crecimiento
n
10
100
1000
k
k
k
k
log(n)
3
6
10
n
10
100
1000
nlog(n)
30
600
10000
n2
100
10000
1000000
n3
1000
1000000
109
2n
1000
1030
10300
Ejemplo: ordenación
• Complejidad en notación asintótica de los
algoritmos de ordenación básicos
– Algoritmo de la burbuja (Bubble Sort)
– Ordenación por inserción (Insertion Sort)
– Ordenación por selección (Selection Sort)
Doble bucle
• ¿Cuál es la complejidad de la suma
1+2+3+…+n?
• Ejemplo del Principio de Inducción:
1+2+3+…+n = n(n+1)/2
• ¿Notación asintótica?
Funciones recursivas
• Establecer la ecuación de recurrencia:
– Complejidad en el caso base
– Complejidad en el caso recursivo
• Expandir la complejidad en el caso base en
función del número de llamadas recursivas
hechas
• Encontrar el número de llamadas necesarias
para estar en el caso base
Ejemplo: Factorial
• Ecuación de recurrencia:
– T(n) = a, n = 0
– T(n) = b + T(n-1), n > 0
• Expandir en el caso recursivo:
Llamadas recursivas
1
2
k
T(n)
b + T(n-1)
2b + T(n-2)
kb + T(n-k)
Ejemplo: Factorial
• T(n) = kb + T(n-k)
• Para eliminar la dependencia de T(), escoger k
tal que estamos en el caso base
• Si k=n, T(n-k) = T(0) = a
• Si substituimos k=n en la expresión,
obtenemos T(n) = bn + a
• ¿Notación asintótica?
Ejemplo: Búsqueda binaria
funcion BB(V:vector; i,d,k:natural)
devuelve booleano
si (i = d) entonces
devuelve (V[i] = k);
sino si (V[(i+d)/2] < k) entonces
devuelve BB(V, (i+d)/2 + 1, d, k);
sino
devuelve BB(V, i, (i+d)/2, k);
fsi
ffuncion
Ejemplo: Búsqueda binaria
• Ecuación de recurrencia (medida n=d – i):
– T(n) = a, n = 0
– T(n) = b + T(n/2), n > 0
• Expandir en el caso recursivo:
Llamadas recursivas
1
2
k
T(n)
b + T(n/2)
2b + T(n/4)
kb + T(n/2k)
Ejemplo: Búsqueda binaria
• T(n) = kb + T(n/2k)
• Para eliminar la dependencia de T(), escoger k
tal que estamos en el caso base
• Problema: n/2k = 0 => 2k = 
• Idea: escoger n/2k = 1  k = log(n)
• T(n) = b*log(n) + T(1) = b*log(n) + b + a
• ¿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 + c*n + 2T(n/2)
Ejemplo: Mergesort
Llamadas
1
2
k
T(n)
b + cn + 2T(n/2)
3b + 2cn + 4T(n/4)
(2k-1)b + kcn + 2kT(n/2k)
• n/2k = 1  k = log(n)
• T(n) = bn + cnlog(n) + an
• ¿Notación asintótica?
Un experimento
• Ordenar mil millones de elementos
• Procesador con frecuencia 1GHz
• Tiempo de ejecución aproximado
– Bubble (Insertion, Selection) Sort: O(n2)
– Mergesort: O(nlog(n))
• log(109)  30
• 109 segundos  ¡32 años!
Ejemplo: Quicksort
• Caso mejor: como Mergesort
• Caso peor: ¡como Bubble Sort!
• Caso promedio: como Mergesort
Descargar

Diapositiva 1