Complejidad de los algoritmos (II)

Como prometía ayer, hoy unos ejemplos de la complejidad de los algoritmos.

O(n)

Imaginemos el siguiente programa (en pseudocódigo):

haz n veces
x=x+1

Cuanto mayor sea n, más veces se ejecutará la instrucción, y por tanto más tardará, de una forma completamente lineal. Si aumentamos n mil veces, el programa tardará mil veces más en ejecutarse.

O(n^2)

Ahora miremos el siguiente programa:

haz n veces
haz m veces
x=x+1

Este programa ejecuta la instrucción n*m veces. Si n y m son iguales, tenemos n². Según incrementamos n, el tiempo de ejecución aumenta cuadráticamente. Si aumentamos n en mil, el tiempo de ejecución aumenta en un millón.

Un ejemplo fuera de la programación de este tipo de algoritmos es el que usamos para hacer multiplicaciones de varias cifras a mano. Con el aumento de cifras aumenta cuadráticamente los pasos a realizar.

O(log(n))

Este ejemplo es algo más complicado, así que voy a hacerlo en dos pasos. Imaginemos que queremos buscar en una lista ordenada de números enteros si está un elemento. (Vamos a evaluar el caso peor, que no dicho elemento no está, ya que es algo bastante típico en programación y es lo que nos da una medida de lo lento que puede ser nuestro algoritmo).

Una forma simple de buscar en la lista es la siguiente:

Mira el elemento i de la lista
¿Es el elemento i de la lista igual a lo que estábamos buscando?
Si es así, terminamos
Si no, habrá que volver al principio

Se le puede hacer alguna modificación, como decirle que ya que está ordenada, detener la ejecución si el elemento que buscamos es mayor que el elemento que estamos mirando, pero en esencia es lo mismo, el caso peor es lineal. Si incrementamos el tamaño de la lista el tiempo de ejecución aumenta linealmente.

Vamos ahora a aprovechar que la lista está ordenada y hagamos algo más inteligente:

Coge la lista y pártela por la mitad
Comparo el elemento que quiero encontrar con las dos mitades
Si el elemento es menor que la segunda mitad, descarto la primera mitad y repito el procedimiento con la segunda mitad
Si el elemento es mayor que la segunda mitad, descarto la segunda mitad y repito el procedimiento con la primera mitad
Si el elemento es igual a uno de los extremos de las dos listas, he terminado, he encontrado lo que buscaba

Este caso va descartando mitades. Por tanto, si tengo n elementos al principio, en la siguiente vuelta tendré n/2, en la siguiente n/4, en la siguiente n/8. En la vuelta k tendré n/(2^k). Y la cosa terminará cuando me quede un elemento, es decir, cuando n/(2^k)=1, cuando k=log(n) (recordad que log lo uso para decir logaritmo en base 2). Por tanto si incremento n, se incrementan los pasos en log(n). Como la función log crece más lentamente que la función líneal, el programa es mucho más rápido.

En el caso de búsqueda lineal, si incremento la lista mil veces, el programa tarda mil veces más. En cambio, en la búsqueda binaria sólo tarda diez veces más. Ese es el objetivo de todos los programas, que tengan complejidad logarítmica.

O(2^n)

Ahora vamos con el caso peor. Para ello vamos a introducir las series de Fibonacci, que se explican de la siguiente manera:

1, 1, 2, 3, 5, 8, ...

Es decir, empieza con 1, 1, y los siguientes elementos son la suma de los dos anteriores.

Una forma muy simple de generar el elemento n de esta serie es:

i es tres
elemento uno es uno
elemento dos es uno
bucle que para cuando i es igual a n
elemento i es elemento i-1 más elemento i-2

Claramente esto se hace en tiempo lineal. Cuanto más grande es n, más operaciones se hacen y se incrementan de forma lineal.

En cambio podemos usar la recursividad:

función fibonacci que requiere el número de elemento a ser calculado (n)
si el elemento es uno o dos, devolver el valor uno
de lo contrario el resultado es el dado por la suma de la función fibonacci de los elementos n y n-1

Es decir, para calcular un elemento llamamos a la misma función dos veces. Cada una de dichas funciones se llama a si misma otras dos veces, etc. Es decir, crece exponencialmente. Lo demuestro:

paso 1: 2 ejecuciones
paso 2: 2* (2 ejecucuciones)
paso 3: 2*(2*(2 ejecuciones))
paso k: (2^k) ejecuciones

¡Esto hay que evitarlo a toda costa! Pero no la recursividad en sí, sino dos llamadas recursivas que se encadenan. Si incrementamos los datos en mil el aumento de tiempo para el cálculo es mayor que la edad del universo.

Un ejemplo de un algoritmo exponencial es factorizar un número. Con algunas técnicas se ha logrado reducir, pero sigue siendo bastante exponencial. ¿Qué consecuencia tiene esto? Pues que multiplicar es fácil, pero separar en números primos no, así que esto se usa para compartir información de forma segura por Internet. Hace tiempo escribí sobre este tema en el blog.

Resumiendo, mirando nuestros algoritmos somos capaces de determinar cuál es la complejidad intentar evitar que sean cuadráticos o, sobretodo, exponenciales.



Tags Technorati: curiosidades, programación, informática