Análisis de complejidad

©César Arturo Cepeda García.  Última modificación 23 abril 2004.

INTRODUCCION

Cuando se analiza y compara el desempeño de diferentes algoritmos, se presta una especial atención al tiempo de corrida del algoritmo.  El tiempo de corrida de un algoritmo, se entiende como el tiempo que le toma al algoritmo calcular el resultado a partir de los datos de entrada.

¿Por qué es importante el tiempo de corrida de un algoritmo?  Porque si conocemos o al menos tenemos una idea del tiempo de corrida de un algoritmo podemos saber que tanto va a tardar en entregarnos la respuesta, y podemos decidir, si la esperamos, nos vamos a tomar un café o si mejor regresamos después de una semana.

Aunque las computadoras de hoy en día son muy rápidas comparadas con sus similares de hace algunos años, y son capaces de llevar a cabo millones de operaciones en un segundo, resulta fácil encontrar ejemplos de problemas y soluciones que tardarían años en solucionarse.

Cuando se analiza el tiempo de corrida de un algoritmo, mas que el tiempo exacto que tardará el algoritmo en milisengudos, lo que importa es la función de crecimiento del algoritmo, la función de crecimiento de un algoritmo, nos da una idea de que tanto aumentará el tiempo de corrida según aumente el tamaño de la entrada.   Por lo general, la función de crecimiento de un algoritmo se expresa como la multiplicación de una constante y una función que depende del tamaño de la entrada, es decir, c f(n) donde n es el tamaño de la entrada.

Tomemos por ejemplo el problema de ordenar una lista de números.  Se tiene un conjunto de números A{x1, x2, ... , xn} un algoritmo de ordenación debe entregar como salida una permutación del conjunto A tal que xi <= xj para cualquier i < j.   Es decir debe ordenar los números del conjunto de chico a grande.

Ordenar una lista de números es quizá la operación más común en las computadoras, cientos de programas ordenan datos para poder trabajar con ellos, debido a eso, la cantidad de algoritmos de ordenación que hay es muy grande, así como el tiempo que se ha dedicado a estudiarlos, muy extenso.  Para este apunte de análisis de complejidad vamos a estudiar principalmente 2 de los algoritmos más famosos de ordenación.  La ordenación por inserción(Insertion Sort) y la ordenación por mezcla(Merge Sort).

La ordenación por inserción tiene una función de crecimiento f(n) = n², mientras que la ordenación por mezcla tiene una función de crecimiento f(n) = n lg n donde lg n representa el logaritmo base 2 de n.  Para demostrar el porque es necesario estudiar el análisis de complejidad, comparemos estos dos algoritmos.  Supongamos que el mejor programador del mundo implemento la ordenación por inserción en lenguaje máquina logrando una constante de 2, por lo que el tiempo total de corrida será T=2 n², donde n representa la cantidad de números que queremos ordenar.  Ahora supongamos que un programador promedio implementa la ordenación por mezcla utilizando un lenguaje de alto nivel obteniendo una constante de 50, por lo tanto el tiempo total de corrilda de la ordenación por mezcla será de T=50 n lg n.  Supongamos además que tenemos una computadora capaz de ejecutar 10,000,000 de operaciones por segundo. 

Comparemos ahora el desempeño de ambas soluciones, supongamos primero que queremos ordenar 1000 números.

Tinsersión = 2 (1000)² = 2,000,000  => 0.2 segundos

Tmezcla = 50 (1000) (11) = 550,000 => 0.055 segundos

Como se observa, el desempeño de la ordenación por mezcla es mucho mejor, la diferencia se va haciendo más drástica conforme varía el tamaño de la entrada, por ejemplo si quisieramos ordenar 100,000,000 de números los tiempos serían

Tinsersión = 2 (100000000)² = 20,000,000,000,000,000       un poco mas de 63 años!!!!!!!

Tmezcla = 50 (100000000) (27) = 135,000,000,000               3 horas con 45 minutos.

Mientras que la ordenación por inserción tomaria todo el resto de sus vidas, la ordenación por mezcla apenas y necesitaria menos de 4 horas.  Por eso vale la pena analizar un algoritmo antes de implementarlo!

ORDENACION POR INSERCION

La ordenación por inserción es un algoritmo eficiente para ordenar pequeñas cantidades de elementos.  La ordenación por inserción funciona de la misma manera que la mayoria de las personas ordena una mano de barajas.  Se comienza con una la mano izquierda vacia, y la mano de barajas, boca abajo en la mesa.  Entonces vamos recogiendo una a una las barajas de la mesa y las insertamos en la posición correcta en la mano izquierda.  Para encontrar la posición correcta, comparamos la nueva baraja con las que tenemos en la mano, de derecha a izquierda.  En todo momento, las barajas que tenemos en la mano izquierda se encuentran ordenadas.

A continuación presentamos un pseudocódigo para implementar el ordenamiento por inserción, nuestro procedimiento toma como entrada un arreglo A[1..n] que contiene una secuencia de elementos de longitud n. 

El código funciona de la siguiente manera, inicialmente tenemos el arreglo A con los elementos desordenados.  Como se explico en el primer párrafo la ordenación por inserción busca siempre tener ordenada la parte izquierda del arreglo, e ir tomando uno a uno los elementos del lado derecho para insertarlos en su posición.

En la línea 1 del algoritmo, tenemos un ciclo que irá moviendo j desde 2 hasta el numero de elementos de A en este caso denotado por Longitud(A). ¿Por qué desde 2?  Recordemos que al inicio tenemos el lado izquierdo vacio y tomamos elementos del lado derecho para insertarlos en su posición correcta.  Sin embargo la posición del primer elemento es trivial, ya que un conjunto de 1 elemento siempre está ordenado!  Por lo tanto no tiene caso buscar la posición del primer elemento.   

Para cada índice, a partir del 2, el elemento que se está insertando se compara con los elementos ya ordenados de derecha a izquierda con el ciclo mientras de la línea 4.  Aqui pueden suceder dos cosas, si el elemento que se está insertando es menor que el elemento ordenado, entonces el elemento ordenado se recorre un lugar hacia la derecha (asignación de la línea 5).  Si el elemento que se está insertando es mayor o igual, entonces se coloca en ese lugar (asignación de la línea 8).   Una vez que se encontro la posición del elemento, se avanza al siguiente índice.  Cuando j sea igual a Longitud(A) + 1 el algoritmo termina y tenemos que los elementos en A están ordenados.

Para que puedas apreciar mejor el funcionamiento de este algoritmo te recomendamos seguirlo en papel con un arreglo de unos 5 números.

Revisemos ahora el costo computacional de ordenar por medio de la técnica de inserción, para esto revisemos de nuevo nuestro código

Para este ejemplo usamos la notación SUM(a,b,f(j)), que significa, la sumatoria desde j=a, hasta j=b de la función f(j).

Para analizar un algoritmo, los pasos a seguir son basicamente 2,  el primer paso es asignar un costo computacional a cada línea del código, este costo computacional, que en la tabla esta representado por c1, c2, ... , c7, está determinada por la velocidad de la máquina y la naturaleza de la función, por ejemplo una suma requiere menos tiempo que una multiplicación.  Determinar este costo no es sencillo, ya que varía de máquina a máquina y de arquitectura a arquitectura, por lo que muy rara vez se hará de manera exacta, sin embargo vale la pena tener presente que existe.  El segundo paso es ver cuantas veces va a ser ejecutada cada línea de código, y está es la parte que más nos interesa, por lo que la analizaremos paso a paso para nuestro ejemplo.

• La línea 1 se ejecuta una vez por cada índice del arreglo, esto es desde 2 hasta Longitud(A)+1 por lo que en total será ejecutado n veces, donde n  es el número total de elementos del arreglo.
• Las líneas 2,3 y 8 se ejecutan el mismo número de veces que la 1 menos uno.  Hay que recordar que el ciclo desde (for), hace una última revisión para el caso en el que ya no cumple con la condición.  Por lo tanto estas líneas se ejecutan n-1 veces.
• Entramos ahora a las líneas 4, 5 y 6 del algoritmo, estas líneas son las que se encargan de buscar la posición correcta del elemento j.  Si recordamos el funcionamiento del algoritmo, para cada índice j se recorre la parte del arreglo ordenada de derecha a izquierda buscando su posición, en el momento en que se encuentra su posición se termina el ciclo mientras.  Por lo tanto la función f(j) dependerá de cuantas comparaciones se tengan que hacer para encontrar la posición del elemento j.

Como puede verse del último punto del analisis, la cantidad de veces que se ejecutan las líneas 4, 5 y 6 no es fijo, sino que depende de la entrada.  En la mayoría de los algoritmos, el tiempo de ejecución dependerá de la entrada, por lo que la mayoria de las veces se puede hacer un análisis de peor caso y análisis del caso promedio.  En la teoría de la computación lo más importante es el análisis del peor caso, este análisis busca cual sería el tiempo de corrida del algoritmo con la peor entrada posible.   Al obtener este tiempo, nos damos una idea de que es lo más que puede llegar a tardar nuestro algoritmo.

Para el caso de la ordenación por inserción, puede verse que el peor caso posible es que la entrada estuviera ordenada en orden inverso, es decir, de grande a chico y nosotros lo queremos ordenar de chico a grande, ya que en este caso, las líneas 4, 5, 6 se ejecutarían j-1 veces para cada índice.  En este caso el tiempo total de corrida sería:

T=c1*n + (c2 + c3 + c7)*(n-1) + c4*SUM(2,n,j) + (c5 + c6)*SUM(2,n,j-1)

Sabemos que: SUM(2,n,j)=( n² + n)/2 - 1   y que  SUM(2,n,j-1)=( n² - n)/2  por lo que si sustituimos tenemos que el tiempo total de corrida del peor caso seria:

T=c1*n + (c2 + c3 + c7)*(n-1) + c4*(( n² + n)/2 - 1 ) + (c5 + c6)*(( n² - n)/2 )

Para facilitar el análisis, consideremos que todas las constantes tienen el mismo valor, es decir c1=c2=c3=c4=c5=c6=c7=c entonces nos queda que

T=c*n + (3c)*(n-1) + c*(( n² + n)/2 - 1 ) + (2c)*(( n² - n)/2 )

T=1.5cn² + 3.5cn - 4c 

Donde se puede apreciar claramente que el tiempo de corrida del ordenamiento por inserción en el peor caso es una función cuadratica de n.  

Cuando se analizan algoritmos, en general sólo importa el termino de la función que crece más rápido, y se eliminan las constantes, por lo tanto en el caso del ordenamiento por inserción, el término que crece más rápido es el término cuadrático, por lo que se dice que el ordenamiento por inserción tiene una complejidad de O(n²).

Es conveniente que revises todo este análisis una y otra vez hasta que lo entiendas perfectamente, ya que el analizar la complejidad de tus algoritmos es muy importante en las ciencias de la computación y por lo tanto en la olimpiada.

ORDENACION POR MEZCLA

La ordenacion por mezcla (MergeSort) utiliza un acercamiento al problema de ordenación muy diferente al utilizado por la ordenación por inserción.  El ordenamiento por mezcla utiliza la técnica de Divide y Vencerás. La técnica de Divide y Vencerás utiliza basicamente tres pasos:

1. Divide: Dividir el problema en un cierto número de subproblemas.

2. Vence: Soluciona los problmeas de manera recursiva.  Si el tamaño de los subproblemas es suficientemente pequeño, simplemente resuelvelos de la manera mas obvia.

3. Combina: Combina el resultado de los subproblemas para obtener la solución al problema original.

La ordenación por mezcla se apega estrictamente a la técnica.  La idea del  algoritmo es la siguiente:

1. Divide: Divide la secuencia de n elementos en dos subsecuencias de n/2 elementos.

2. Vence: Ordena ambas subsecuencias de manera recursiva.

3. Combina:  Mezcla las dos subsecuencias ordenadas para obtener la solución del problema.

Para la solución recursiva cada subsecuencia a su vez se divide en dos sub-subsecuencias, y así hasta obtener una subsecuencia de tamaño 1, en este momento se detienen la recursión, ya que una subsecuencia de tamaño uno,  siempre está ordenada.

La clave del ordenamiento por mezcla es precisamente la rutina que mezcla las dos subsecuencias ordenadas en una subsecuencia ordenada en el paso de Combinación. En este ejemplo usaremos para esa función un procedimiento llamado Mezcla(A,p,q,r) donde A es un arreglo y p, q y r son índices del arreglo tales que p <= q < r.  El procedimiento asume que los subarreglos A[p..q]  y  A[q + 1..r] están ordenados.  El procedimiento mezcla estos dos subarreglos para formar un único arreglo ordenado en A[p..r].

Para explicar como funciona el procedimiento Mezcla volvamos al ejemplo de las barajas.  Supongamos ahora que se tienen dos montones de barajas, ordenados con las barajas hacia arriba, y deseamos mezclarlos en un único montón ordenado con las barajas hacia abajo.  Al inicio ambos montones tienen a su carta más chica hasta arriba, el paso básico de nuestro algoritmo es comparar las barajas en la parte superior de cada montón, retirar la que sea más chica y ponerlas en nuestro montón de salida.  Al quitar una baraja de uno de los montones, queda expuesta la siguiente baraja, por lo que podemos seguir, si alguno de los montones se llegara a terminar, entonces tomamos el montón que quedo y lo ponemos todo en nuestro montón de salida y listo, terminamos!  

A continuación implementamos el procedimiento Mezcla.  Aunque este procedimiento no se analizará tan minuciosamente como el del ordenamiento por inserción, debe poder verse que su complejidad es de O(n) donde n=r - p + 1, es decir el número total de elementos a mezclar.  Esto se debe a que cada elemento de cada uno de los dos submontones, se movio al montón de resultado únicamente una vez, por lo que si hay n elementos, el procedimiento tardará un tiempo proporcional a n.

 En resumen, el procedimiento Mezcla funciona como sigue:

• Las líneas 1 y 2 calculan el largo del primer y segundo sub-arreglos.

• Las líneas 3 y 4 apartan memoria suficiente para los dos sub-arreglos.

• Los ciclos desde de las líneas 5, 6, 7 y 8 copian ambos sub-arreglos a los arreglos L y R.

• En las líneas 9 y 10 se inicializa el último término de L y R a infinito, esto es muy importante, ya que aqui el infinito nos sirve para saber cuando ya se terminó uno de los sub-arreglos.  Aunque en cuestión práctica no existe tal cosa como "infinito" en las computadoras, se suele usar algún valor que previamente hayamos establecido como nuestro "infinito".
• El ciclo desde que inicia en la línea 13 va desde p hasta r, es decir se ejecuta un número de veces igual a la suma de los elementos de ambos sub-arreglos.  El funcionamiento de este ciclo es la idea básica del algoritmo.  Compara el primer elemento no mezclado de cada sub-arreglo y retira el menor, avanzando hacia el siguiente elemento del sub-arreglo de donde se retiro el elemento.

Con el procedimiento Mezcla podemos implementar nuestra ordenación por mezcla.  El código del algoritmo queda de la siguiente forma

Como vimos anteriormente, la técnica de divide y vencerás se basa en tres pasos básicos.  Como con la ordenación por inserción sea T(n) el tiempo total que tarda el algoritmo en ordenar n elementos.  Cuando n es suficientemente chico, digamos n <= c, entonces resolvemos el problema de la manera obvia, para este caso nuestro programa tarda un tiempo constante, por lo que podemos decir que tiene una complejidad de O(1).  En general, supongamos que la division de nuestro problema nos entrega a subproblemas, cada uno de tamaño 1/b (para el caso de la ordenación por mezcla, tanto a como b son iguales a 2).  Si tomamos que D(n) es el tiempo que tardamos en dividir el problema en subproblemas, y C(n), el tiempo que tardamos en combinar los subproblemas en una solución, entonces tenemos que

Hay un "teorema maestro" que sirve para resolver recurrencias de esta forma, sin embargo para varios casos, como el de la ordenación por mezcla, se puede ver de manera intuitiva cual va a ser el resultado.  Revisemos paso a paso cada una de las partes.

• Dividir: Para dividir, basta con cálcular cual es la mitad del arreglo, esto, se puede hacer sin ningún problema en tiempo constante, por lo que tenemos que para la ordenación por mezcla D(n) = O(1)

• Vencer: Como dividimos el problema a la mitad y lo resolvemos recursivamente, entonces estamos resolviendo dos problemas de tamaño n/2 lo que nos da un tiempo T(n) = 2T(n/2)

• Combinar: Vimos anteriormente que nuestro Mezcla era de orden lineal, por lo que tenemos que C(n)=O(n)

Para sustituir, sumamos D(n) + C(n) = O(n) + O(1) = O(n), recordemos que para el análisis de complejidad únicamente nos importa el término que crezca más rápido.  Por lo que sustituyendo en la recurrencia tenemos que:

donde c representa una constante igual al tiempo que se requiera para resolver un problema de tamaño 1.

Sabemos que n sólo puede ser dividido a la mitad lg n veces, por lo que la profundidad de nuestra recursión será de lg n, también del funcionamiento del algoritmo podemos ver que cada vez que dividamos a la mitad, vamos a tener que mezclar los n elementos, y sabemos que mezclar n elementos nos toma un tiempo proporcional a n, por lo que resolver la recursión debe tomar un tiempo proporcional a n lg n, que de hecho es la complejidad del algortimo.  La ordenación por mezcla tiene una complejidad de O(n lg n).

Podemos comprobarlo, sustituyendo valores en la ecuación de recurrencia. 

De la tabla anterior vemos que el tiempo real de corrida del ordenamiento por mezcla es proporcional a n lg n + n, de nuevo, como en el análisis de complejidad únicamente nos importa el término que crezca más rápido y en ésta función ese término es n lg n, por lo tanto la complejidad del sistema es O(n lg n).

CONCLUSIONES

Es muy importante que siempre que piensen un algoritmo, realicen un análisis de complejidad de su algoritmo, aunque no todos los algoritmos son tan sencillos de analizar, para la mayoría es fácil determinar la función de crecimiento del mismo.

Determinar la complejidad de su algoritmo les puede dar una idea muy clara de cuanto tiempo va a tardar el mismo, y en base a los tamaños de la entrada podrán determinar si su programa correrá en tiempo o no.