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 |