Eficiencia de los Algoritmos Computacionales

¿Qué es un algoritmo? “(del árabe al-Khowârizmî, sobrenombre del célebre matemático árabe Mohámed ben Musa). Conjunto ordenado y finito de operaciones que permite encontrar la solución a un problema…” Un algoritmo, puede expresarse en términos de un lenguaje de programación, para obtener un programa que resuelve el problema por medio de la computadora.

Cita... “No hay un incremento concebible en el poder de las computadoras que pueda saturar la demanda científica: aún pensando que una computadora posea un ciclo de tiempo subnuclear (10-23 seg.) y densidades de almacenamiento subnucleares (1039 bits/cm3), ésta no podría manejar la mayoría de los problemas que son importantes en la investigación científica básica y aplicada. Por lo tanto, existirá siempre una fuerte presión para incrementar la eficiencia de los programas, para poder incrementar también la cantidad de información últil generada por un programa.” Ken Wilson, Nóbel de Física 1982

Áreas de estudio ¿Cómo construir algoritmos? Técnicas de diseño ¿Cómo expresar algoritmos? Enfoques de los lenguajes de programación ¿Cómo validar algoritmos? Verificación formal ¿Cómo analizar algoritmos? Complejidad computacional, eficiencia, legibilidad, usabilidad, etc...

Análisis de algoritmos Si se tuvieran 2 programas que hacen lo mismo, ¿cómo se podrían comparar? 1. Eficiencia: Tiempo de ejecución Uso de espacios de memoria 2. Facilidad de lectura, mantenimiento, rapidez para codificarlo.

Medición del tiempo de ejecución El tiempo de ejecución depende de: 1. La entrada al programa: Su tamaño Sus características 2. La calidad del código generado para el programa por el compilador . 3. La rapidez de las instrucciones de máquina. 4. La complejidad de tiempo del algoritmo.

¿Cómo medir? Cantidad de instrucciones básicas (o elementales) que se ejecutan. Ejemplos de instrucciones básicas: asignación de escalares lectura o escritura de escalares saltos (goto’s) implícitos o explícitos. evaluación de condiciones llamada a funciones etc.

Ejemplo cont = 1; while (cont <= n) do { x = x + a[cont]; x = x + b[cont]; cont = cont + 1; } 1 n+1 n n n n (goto implícito) 1 goto en falso. TOTAL: 5n + 3

Ejemplo z = 0; for (int x=1; x<=n; x++) for (int y=1; y<=n; y++) z = z + a[x,y]; 1 1 asignación + (n+1) comparaciones (n+2)*n = n2 +2n n*n = n2 2n2 (incremento + goto implícito) n (goto en falso for y) 2n (incremento + goto implícito) 1 (goto en falso for x) TOTAL: 4n2 + 6n + 4

Consecuencia… Se requiere contar con una notación que permita comparar la eficiencia entre los algoritmos… La NOTACIÓN ASINTÓTICA es la propuesta de notación aceptada por la comunidad científica para describir el comportamiento en eficiencia (o complejidad) de un algoritmo. Describe en forma sintética el comportamiento de la función que con la variable de entrada, determina el número de operaciones que realiza el algoritmo.

NOTACIÓN ASINTÓTICA COMPLEJIDAD TEMPORAL (y ESPACIAL). Tiempo (o espacio) requerido por un algoritmo, expresado en base a una función que depende del tamaño del problema. COMPLEJIDAD TEMPORAL ASINTÓTICA (y ESPACIAL). Comportamiento límite conforme el tamaño del problema se incrementa. Determina el tamaño del problema que puede ser resuelto por un algoritmo.

Definición Se dice que la función f(n) “es de orden g(n)” [O(g(n))], si existen constantes positivas c y n0 tales que f(n) <= c g(n) cuando n >= n0 Ejemplos: n+5 es O(n) pues n+5 <= 2n para toda n >= 5 (n+1)2 es O(n2) pues (n+1)2 <= 4n2 para n>= 1 (n+1)2 NO es O(n) pues para cualquier c > 1 no se cumple que (n+1)2 <= c*n

Ordenes más comunes de los algoritmos O(1) Constante O(n) Lineal O(n2 ) Cuadrático O(n3 ) Cúbico O (nm ) Polinomial O(log(n)) Logarítmico O(nlog(n)) nlog (n) O(mn ) exponencial O(n!) factorial

Comportamiento de las funciones log n n n log n n sqrt(n) n2

Otro método para calcular el orden de un problema Consiste en aplicar reglas a los estatutos estructurados: Secuencia de instrucciones Decisiones (ejemplo: if) Ciclos (ejemplo: while) Recursividad

Regla 1: Secuencia de instrucciones Ejemplo: Una secuencia de 3 ciclos: Ciclo 1 = O(n) Ciclo 2 = O(log n) Ciclo 3 = O(n2) Tendrá como orden total… O(n2). O(g1(n)) O(g2(n)) O(g3(n)) O(gm(n)) ˜ O( mayor(g1(n), g2(n), …, gm(n) )

Regla 2: Decisiones Ejemplo: Una decisión con: Rama then = O(n log n) Rama else = O(log n) Tendrá como orden total… O(n log n). O(g1(n)) O(g2(n)) ˜ O( mayor(g1(n), g2(n)) )