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
(Gp:) n
(Gp:) T(n)
(Gp:) f(n)
(Gp:) c*f(n)
(Gp:) N
O(f(n)) = {T(n) : ?c,N, ?n>N, T(n) < c*f(n)}
Funciones típicas
Velocidad de crecimiento
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?
Página siguiente  |