LA NOTACIÓN ASINTÓTICA EN EL CÓMPUTO CIENTÍFICO
RESUMEN PALABRAS CLAVE Algoritmos, Complejidad Computacional, Análisis Asintótico, Cómputo Científico, Optimización. ABSTRACT KEYWORDS Algorithms, Computational Complexity, Asymptotic Analysis, Scientific Computing, Optimization 1 Introducción 2 Importancia de la notación asintótica Por ejemplo, consideremos a los algoritmos de ordenamiento, muy utilizados cotidianamente en el mundo para ordenar grandes cantidades de información, ya sea por orden alfabético, cronológicamente, o por valores de menor a mayor (o viceversa); estos tipos de ordenamientos son muy utilizados por los gobiernos, bancos y grandes empresas en general. Existen diferentes técnicas para dichos ordenamientos, el método más sencillo y antiguo es el de la burbuja (o Bubblesort), que también es el más ineficiente, donde cada elemento se compara con todos para definir su posición destino; es decir, se requieren n comparaciones para cada uno de los n elementos, esto es Esto se debe precisamente a las constantes que se omiten en los análisis de los tiempos de ejecución, el término 3 ¿Es realmente importante buscar siempre el algoritmo óptimo?
Sin embargo, en el cómputo científico donde se manejan cantidades enormes de datos en super computadoras, generalmente es muy importante trabajar con los algoritmos más eficientes posibles; ya que cada minuto de uso de las supercomputadoras representa miles de dólares. En estos casos como la cantidad de datos de entrada a los programas es muy grande, la razón o tasa de crecimiento del algoritmo a usarse afecta bastante el tiempo reloj total de ejecución, en el rango de las horas, días o hasta meses según sea el caso. 4 Determinando el tiempo de ejecución Es algo así como las resistencias en los circuitos eléctricos, las resistencias negativas no existen a menos que estas contengan una fuente de poder, de lo contrario se violaría la ley de conservación de la energía. Usando funciones negativas en el análisis asintótico del tiempo de corrimiento de un algoritmo o programa de computadora, corremos el riesgo de cometer errores como el siguiente: 4.1 Cálculo del tiempo de ejecución de programas de computadora (1) for i in range(0, n):
La línea 3 se ejecuta en un tiempo constante u
Este segmento de código busca a lo largo de un vector de datos un elemento con el mismo valor que z. Es probable que encuentre dicho elemento en el primer paso, o en el último, o nunca. Como tenemos que basarnos siempre en el peor caso, decimos que este segmento de código se ejecuta en un tiempo de orden 4.2 Tiempo de ejecución de programas en paralelo 4.3 El uso de T(n) para el análisis
(1)
Desarrollando y reduciendo la ecuación obtenemos (2)
Haciendo una recursión mas tenemos (3)
Este proceso de expansión lo podemos hacer log n veces, resultándonos
(4)
Estas recurrencias se pueden resolver también usando el teorema maestro [8], aunque este tiene sus limitaciones y no puede ser utilizado en todos los casos. 5 Los límites asintóticos 5.2 Notación Theta 5.3 Notación “o” pequeña (5)
5.4 Notación Omega minúscula (6)
Por ejemplo, Figura 1. La presente gráfica muestra una comparación entre los diferentes tipos de notaciones, mostrándose como aumenta la carga computacional respecto al incremento de los datos de entrada. 6 Conclusiones Otro factor es que no es confiable usar el tiempo reloj como medida del tiempo de ejecución de los algoritmos. Esto se debe a que en una misma computadora para un mismo algoritmo, el tiempo reloj puede variar bastante dependiendo de diversos factores, como lo son el sistema operativo o la ejecución de ciertas interrupciones o procesos que se salen del control del usuario. Estas variaciones pueden ser bastante más significativas si se compara el tiempo de ejecución de programas en máquinas con capacidad distinta o con arquitecturas diferentes. Por ello la trascendencia en el uso de la notación matemática en todos los análisis de algoritmos.
Referencias bibliográficas [1] Baase, S. (1988): “Computer algorithms: introduction to design and analysis” (2nd ed.). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA. [2] Bahi, J. M., Contassot-Vivier, S., and Couturier, R. (2007): “Parallel Iterative Algorithms: From Sequential to Grid Computing” (Chapman & Hall/CRC Numerical Analy & Scient Comp. Series). Chapman & Hall/CRC. [3] Brassard, G., and Bratley, P. (1996): “Fundamentals of algorithmics”. Prentice-Hall, Inc., Upper Saddle River, NJ, USA. [4] Cárdenas-Haro, J. A., Galaviz-Yáñez, G., y Lopez-Mariscal, G. (2005): “Análisis matemático del tiempo de corrimiento y aceleración del algoritmo de ordenamiento quicksort en paralelo”. Memorias de la XV Semana Regional de Investigación y Docencia en Matemáticas (2005), p. 27-32. [5] Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2001): “Introduction to Algorithms”, 2nd Ed. MIT Press, Cambridge, MA, 2001. [6] Dussault, J.P. (1995): “Numerical stability and eficiency of penalty algorithms”. SIAM J. Numerical Analysis. 32, 1 (1995), p. 296-317. [7] Grenet, B., Koiran, P., and Portier, N. (2013): “On the complexity of the multivariate resultant”. Journal of Complexity. Vol. 29, 2 (2013), pp. 142-157. Elsevier. [8] Leighton, T. (1996): “Notes on better master theorems for divide-and-conquer recurrences”. In Lecture notes, MIT (1996). [9] Pan, L., and Prez-Jimnez, M. (2010): “Computational complexity of tissue-like p systems.” Journal of Complexity. Vol 26, 3 (2010), pp. 296-315. Elsevier. [10] Parhami, B. (1999): “Introduction to Parallel Processing: Algorithms and Architectures”. Kluwer Academic Publishers, Norwell, MA, USA, 1999. [11] Urli, T., Wagner, M., and Neumann, F. (2012): “Experimental supplements to the computational complexity analysis of genetic programming for problems modelling isolated program semantics”. In Parallel Problem Solving from Nature - PPSN XII, Vol. 7491 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2012, pp. 102-112. [12] Wang, S. D., Xiao, J. Y., Liu, Z. Q., and Niu, J. L. (2008): “Study on tire imprint image recognition based on FFT image differencing algorithm”. In FSKD (2) (2008), J. Ma, Y. Yin, J. Yu, and S. Zhou, Eds., IEEE Computer Society, pp. 504-508. Fecha de recepción: 17 de enero de 2013 |
es demasiado detallado y se presta a confusiones, esto se vuelve más grave en ecuaciones con mas elementos; lo cual crea la necesidad de utilizar una notación más genérica, sin dejar de ser representativa de la cantidad de recursos computacionales requeridos por la función. Así nace la notación asintótica. En matemáticas la asíntota es una línea que continuamente se aproxima a una curva dada pero nunca la cruza o intersecta. Lo más relevante en el uso de la notación asintótica es para determinar la eficiencia de los algoritmos, es decir, sirve para estimar matemáticamente la cantidad de recursos requeridos en la ejecución de un programa [5] [1] [10] [7] [9] [11]. Específicamente aquí nos estamos refiriendo a recursos de cómputo como son uso del procesador y memoria primaria y/o secundaria. Este tipo de notación se vuelve necesaria ya que no hay una computadora estándar o máquina modelo ideal universal para ser tomada como referencia para medir el tiempo de corrimiento de los algoritmos a usarse en programas de computadora. El análisis de algoritmos también es una herramienta para los diseñadores para estimar si una solución propuesta satisface las restricciones de recursos de un problema. La consideración principal para estimar el desempeño o eficiencia de un algoritmo es la cantidad de operaciones básicas requeridas por dicho algoritmo para procesar o resolver un problema dada una entrada de datos de cierto tamaño. Aquí el concepto de razón de crecimiento es muy importante para analizar y comparar algoritmos. La razón de crecimiento es la tasa a la cual el costo computacional de un algoritmo se incrementa conforme la cantidad de datos de entrada aumenta. Usualmente la cantidad de datos de entrada se especifica con la letra n, que indica el número o cantidad de elementos a procesar por el algoritmo para darnos la solución o respuesta que buscamos.
comparaciones o pasos, lo cual se define asintóticamente como 
. Existen otros algoritmos de ordenamiento que son mucho más eficientes así como complicados como es el caso del Quicksort, Mergesort, Heapsort, Bucketsort, entre otros. Por ejemplo, el tiempo de corrimiento o ejecución del algoritmo Quicksort es 
para el caso promedio (el peor caso es 
pero la probabilidad de que este ocurra es casi cero). El tiempo de ejecución de otros algoritmos como Mergesort o Heapsort es 
siempre, sin embargo en la práctica Quicksort termina en promedio más rápido los ordenamientos.
es un valor general y redondeado que manifiesta solo la parte del algoritmo que consume el máximo de los recursos (mas detalles en la sección 4).
y 
vemos que solo para valores de 
la function 
supera a las otras. Trazando estas funciones vemos que 
y 
son líneas rectas que nunca se cruzan, es decir, se mantienen paralelas. Para un mismo algoritmo, el tamaño de la entrada (o cantidad de datos a analizarse) puede variar bastante según sea el problema a resolver, es por ello y también para simplificar el análisis, que se ignoran las constantes. Lo más importante es enfocarse en examinar la razón o tasa de crecimiento, a esto se le conoce como análisis asintótico. Sin embargo es importante recalcar que hay ciertas circunstancias específicas en donde la razón o tasa de crecimiento no es el criterio primordial a considerar a la hora de diseñar o comparar programas o algoritmos. Mencionamos a continuación algunas situaciones donde se presenta este dilema.
que uno de 
. 
aunque 
cuando 
. Otro ejemplo más general sería con un programa de computadora que se componga de tres partes que sean inicialización, procesamiento y finalización. Supongamos que estas tres partes requieren un tiempo de 
y 
respectivamente. Entonces el tiempo total de corrimiento de dicho programa de computadora sería 
. En otras palabras, el tiempo de corrimiento de un algoritmo o programa de computadora está determinado por la parte que mas consume recursos o tiempo de procesamiento [3]. En cómputo todo este consumo de recursos se define en funciones positivas, no pueden ser funciones negativas.
. Para el tiempo de ejecución de los algoritmos se utiliza la notación asintótica para definir el peor caso, el mejor caso y el caso promedio.
y de acuerdo a la línea 2 del código esto se repite n veces que en total es 
, a su vez las líneas 2 y 3 en conjunto se iteran otras n veces. Es decir, un total de 
operaciones para llenar la matriz con unos. Analicemos ahora este otro segmento de código en Python:
. 
si se hace de manera secuencial; pero en paralelo digamos con n/2 procesadores, el tiempo de ejecución se reduce a 
. Esto es porque cada uno de estos procesadores puede sumar de manera simultanea dos números y reducirse el total de sumandos a la mitad en cada iteración, obteniendo así el gran total de la suma en solo log n pasos. Otro ejemplo es con los algoritmos de ordenamiento donde el Quicksort se ejecuta en un tiempo promedio de 
de manera secuencial, esto es 
comparaciones 
veces [4]. En paralelo tenemos la ventaja de que las 
comparaciones pueden ejecutarse en 
quedando el tiempo promedio total en solo 
. La búsqueda del elemento mayor en un vector de datos se puede realizar de manera secuencial en un tiempo 
, en paralelo este tiempo se reduce a 
ya que todas las comparaciones necesarias pueden hacerse de manera simultanea. En paralelo además del orden del tiempo de ejecución, se habla del orden de trabajo. Si bien el tiempo de ejecución se reduce, al final el trabajo es el mismo solo que distribuido entre varios o muchos procesadores. Podemos decir que el orden de trabajo de un algoritmo en paralelo es igual al orden del tiempo en su versión secuencial. En la sección 4.1 vemos como analizar el tiempo de ejecución en programas secuenciales, en paralelo esto cambia sustancialmente.
como base al hacer el análisis para determinar el tiempo de ejecución en un algoritmo; esta se utiliza para representar las recurrencias en base a la cantidad n de datos a procesarse. Comúnmente en un programa de computadora vamos a tener iteraciones o recursiones, esto es, una función es ejecutada en múltiples ocasiones ya sea porque es llamada desde otra función o porque esta se llama a sí misma. Por ejemplo, en la recurrencia 
se utiliza la técnica divide y vencerás y sirve para el análisis de algoritmos como en la FFT (Transformada Rápida de Fourier, por sus siglas en Inglés, la cual tiene muchas aplicaciones en física e ingeniería [12]), o en algoritmos de ordenamiento como el Quicksort o Mergesort. Si queremos saber cual es su orden de tiempo de ejecución, tenemos que resolverlo recursivamente. Por simplicidad y sin perder generalidad, supongamos que 
donde 
. Expandiendo esta recurrencia tenemos:
o lo que es lo mismo 
si existe una constante real 
y una constante entera 
tal que 
para cada entero 
nos indica simultáneamente los límites superior e inferior de ejecución, cuando estos están determinados (en una misma función) por diferentes múltiplos reales positivos.
si y solo si 
pertenece simultáneamente a 
y a 
. A esto también se le conoce como orden exacto de 
ya que su tiempo de ejecución está acotado por arriba y por abajo al mismo tiempo.
La relación 
nos dice que 
crece mucho más rápido que 
asumiendo que 
y 
son funciones de una variable. Como ejemplo podemos decir que 
En este tipo de notación formalmente está establecido que:
muy raramente se usa en ciencias de la computación. La relación de 
con 
es similar a la relación de la “o” pequeña con la “O” grande en términos asintóticos.
se cumple si para cualquier constante real 
, existe una constante entera 
tal que 
para cada entero 
. Esto implica que:
, pero 
. 
