Análisis de Complejidad Algorítmica - Estructura de Datos y Algoritmos - PDF

Estructura de Datos y Algoritmos EDA Complejidad Algorítmica Eduardo Rosales [email protected] Departamento de Ingeniería de Sistemas y Computación Universidad de los Andes ...

Estructura de Datos y Algoritmos EDA Complejidad Algorítmica Eduardo Rosales [email protected] Departamento de Ingeniería de Sistemas y Computación Universidad de los Andes  Algoritmo ¿Qué es un algoritmo? Secuencia precisa de instrucciones para resolver un problema Las instrucciones deben estar bien organizadas y estructuradas Produce una salida específica para unas entradas dadas Debe garantizarse que terminará Fuente: https://www.flaticon.com 2  Algoritmo Características de un algoritmo Precisión Finitud Cualidades deseadas de un algoritmo Determinismo General Eficiente 3  Motivación Razones para analizar algoritmos: Predecir el desempeño Comparar algoritmos Ofrecer garantías Comprender el soporte teórico Evitar errores de rendimiento (performance bugs) 4  Aplicación Práctica ¿Cuál algoritmo es más eficiente en tiempo para un gran volúmen de datos? ¿Por qué? def busqueda_secuencial(lista, elemento_a_buscar): def busqueda_binaria(lista, elemento_a_buscar): resultado = None resultado = None encontrado = False encontrado = False indice = 0 inicio, fin = 0, len(lista) - 1 while indice < len(lista) and not encontrado: while inicio elemento_a_buscar: fin = medio - 1 return resultado else: resultado = lista[medio] encontrado = True return resultado 5  El Método Científico Método científico: Observar características del mundo natural Formular un modelo acorde con las observaciones Predecir eventos utilizando la hipótesis Verificar predicciones con más observaciones Validar repitiendo el proceso hasta concordancia entre hipótesis y observaciones Principios: Los experimentos deben ser reproducibles Las hipótesis deben ser refutables 6  Método Científico en Análisis de Algoritmos Visión clave (Knuth 1970s): Utilizar el método científico para comprender el rendimiento de algoritmos El método científico es una herramienta para predecir rendimiento y comparar algoritmos ¿Qué medir? ⍻ Número de líneas de código ⍻ Espacio usado en memoria ✓ Tiempo de ejecución 7  Aproximación Teórica El tiempo total de ejecución de un programa está determinado por dos factores primarios: El costo de ejecutar cada instrucción La frecuencia de ejecución de cada instrucción 8  Operación Primitiva Operación primitiva Corresponde a una instrucción de bajo nivel con un tiempo de ejecución constante También llamada, operación de orden constante Idealmente, éste podría ser el tipo de operación básica que ejecuta el hardware 9  Ejemplos: Operaciones Primitivas Operación* Ejemplo Declaración de variables int a = 5 Asignación de valor a = 10 Comparación de enteros a > b Suma de enteros / punto flotante* a + b Multiplicación de enteros / punto flotante* a * b División de enteros / punto flotante* a / b Módulo de enteros / punto flotante* a % b Acceso a elemento de una lista/diccionario lst[i]; dct['clave'] Longitud de una lista/diccionario len(lst); len(dct) * Para números que están dentro de los límites de la representación de punto flotante estándar de 32 o 64 bits 10  ¿Cómo Medir la Complejidad de un Algoritmo? Complejidad temporal Tiempo total de ejecución del programa = Operaciones requeridas por el algoritmo * Tiempo por operación Complejidad espacial Memoria total usada por el programa = Número de objetos usados por el algoritmo * Memoria requerida por objeto 11  ¿Cómo Medir la Complejidad de un Algoritmo? Aproximación teórica (a priori): Determinación (aproximación) matemática No requiere la implementación del algoritmo No depende del hardware o software de soporte Independiente del tamaño de los datos de entrada Aproximación empírica (a posteriori): Observar (medir) su comportamiento Requiere la completa implementación del algoritmo Difícil obtener medidas precisas Dependiente del tamaño de los datos de entrada 12 Midiendo la Complejidad Temporal 13 Ordenes de Crecimiento Temporal Típicos 14 Ordenes de Crecimiento Temporal Típicos 15  Notación Big Theta Big Theta (Θ): Describe un límite asintótico ajustado Indica que un algoritmo tiene un tiempo de ejecución que es tanto superior como inferiormente acotado por una función 16  Notación Big Omega Big Omega (Ω): Define un límite inferior asintótico Se utiliza para describir la complejidad mínima de un algoritmo 17  Notación Big O Big O (O): Establece un límite superior asintótico Se usa para describir la complejidad máxima de un algoritmo Se eliminan los términos de orden inferior y las constantes 18 Ordenes de Crecimiento Temporal Típicos 19  Orden Constante O(1) Orden constante Características Tiempo constante y predecible Independiente del tamaño de los datos Ventajas Simple de entender e interpretar Eficiente para volúmenes de datos muy pequeños Desventajas Ineficiente para grandes volúmenes de datos 20  Orden Constante - Ejemplo: verificar si un número es par def es_par(n): ''' Determina si un número es par o impar. Instrucción Frecuencia Parameters: n (int): el número a verificar. Returns: bool: True si n es par, False si n es impar. ''' return n % 2 == 0 ¿Qué instrucciones se deben analizar? ¿Cuál es su frecuencia? 21  Orden Constante - Ejemplo: verificar si un número es par def es_par(n): ''' Determina si un número es par o impar. Instrucción Frecuencia Parameters: Módulo (%) n (int): el número a verificar. Returns: Comparación (==) bool: True si n es par, False si n es impar. return ''' return n % 2 == 0 ¿Qué instrucciones se deben analizar? ¿Cuál es su frecuencia? 22  Orden Constante - Ejemplo: verificar si un número es par def es_par(n): ''' Determina si un número es par o impar. Instrucción Frecuencia Parameters: Módulo (%) n (int): el número a verificar. Returns: Comparación (==) 1 bool: True si n es par, False si n es impar. return ''' return n % 2 == 0 Módulo y comparación de enteros, y return se consideran operaciones primitivas 23  Orden Constante - Ejemplo: verificar si un número es par def es_par(n): ''' Determina si un número es par o impar. Instrucción Frecuencia Parameters: Módulo (%) n (int): el número a verificar. Returns: Comparación (==) 1 bool: True si n es par, False si n es impar. return ''' return n % 2 == 0 Orden de crecimiento temporal del algoritmo: Notación Big O: O(1) 24  Ejercicio en Clase - Pregunta 2.1 Estimar el orden de crecimiento temporal del algoritmo usando la notación O def dar_elemento_en_posicion(lista, pos): ''' Retorna el elemento en la posición especificada de la lista. Parameters: lista (list): la lista de la cual obtener el elemento. pos (int): la posición del elemento a retornar. Returns: El elemento en la posición dada o None si la posición es inválida. ''' resultado = None if 0