Complejidad de los algoritmos

Complejidad de los algoritmos

Siguiendo con nuestrocurso de programación ya hemos hablado de como diseñar nuestros algoritmos, pero no hemos hablado de como estos repercuten en nuestro sistema. Cuando hablamos de complejidad de los algoritmos hablamos principalmente de dos conceptos:

complejidades_algoritmos

  • La complejidad en si que es para un tamaño n tardará un tiempo y para un tiempo mayor cumplirá f(n2) la complejidad nos describe el tipo de curva que cumplirá esa función f. Esto lo representamos como O(f).
  • El tiempo que tardará para un tamaño n es llamado tiempo de ejecución. Esto es lo representamos como T(n).

Ranking de complejidades

Existe una serie de complejidades que podemos denominar "típicas". En la siguiente tabla las podemos ver ordenadas de mejor a peor:ranking_complejidades

Propiedades fundamentales

Para poder calcular la complejidad de una función o método iterativo debemos aplicar las siguientes propiedades:

  1. O(C·f) = O(f)
  2. Regla de la suma: O(f 1 + f 2 ) = O(max(f 1 , f 2 )).
  3. Regla del producto: O(f 1 ·f 2 ) = O(f 1 )·O(f 2 )
  4. O(log a n) = O(log b n) = O(log n)
  5. O(log(n K )) = O(K·log n) = O(log n)
  6. O(log n·log n·...·log n) = O(log K n) ≠ O(log n)

Ejemplos de calculo de complejidades

A continuación tenemos un par de ejemplos de como sería el tiempo de ejecución y la complejidad del algoritmo para los siguientes problemas:

for (i= 1; i<= n; i++) { O(1) } T(n) = n => O(n)for (i = n; i > 0; i--) { O(1) } T(n) = n => O(n)for (i = 1; i <= n; i += 2) { O(1) } T(n) = n/2 => O(n)for (i = 1; i <= 3*n; i += 2) { O(1) } T(n) = 3n/2 => O(n)for (i= 1; i <= n; i*= 2) { O(1) } T(n) = log (n) => O(log n)for (i= n; i >= 1; i /=2) { O(1) } T(n) = log (n) => O(log n)for (i = 1; i <= n; i*= c) { O(1) } T(n) = log (n) => O(log n)for (i = 1; i <= n*n; i*= 2) { O(1) } T(n) = log (n ) => O(log n)for (i = 1; i <= n*n*n/2; i*= c) { O(1) } T(n) = log (n ) => O(log n)for(i = n/2; i <=n; i++) T(n) = n/2·n/6= n2 / 12 => O(n**2 )      for(j = 1; j <= n/3; j+=2) {O(1)}for (i= 1; i<=n; i++) T(n)= n·n·n= n3 => O(n**3 )      for (j= n; j>=1; j--)            for (k=0; k<n; k++) { O(1) }for (i = 2*n; i >= 0; i -= 3) T(n) = 2n/3 · log2 n3 => O(n log n)      for(j = 1; j <= n*n*n; j *= 2) {O(1)}for (i = n; i >= 1; i /=2) T(n) = ... => O(n log n)      for(j = 1; j <= n/3; j++) {O(1)}for (i = 1; i <=n; i *=3) T(n) = ... => O(log n·log n) = O(log n)      for(j = 1; j <= n*n*n; j*=2) {O(1)}

Si nos fijamos siempre se saca la función que represente la complejidad de la función y no se tienen en cuenta las constantes de complejidad (Reglas 4, 5 y 6). Estamos aplicando en todo momento las reglas antes mencionadas.

Calcular el tiempo de ejecución y el tamaño de un problema

Lo mejor es ver lo mediante un ejemplo. Supongamos que tenemos un método que itera a través de todos los elementos (números) de una matriz bidimensional de orden n, haciendo un cálculo (la complejidad de dicho cálculo es O(1)). Teniendo en cuenta la complejidad de la operación completa:

a) Si para n = 1000 el método tarda 10 minutos, ¿cuánto tiempo tardaría si n = 1000000?

n1= 1000                              t1= 10 minutos           n2= 1.000.000t2= K**2 ·t1                          K= t1 / t2 = 1000t2= 10 6 ·10= 10**7 minutos

b) Si para t = 3 segundos el método pudiera resolver un problema con un tamaño de n = 100, ¿cuál podría ser el tamaño del problema si dispusiéramos de un tiempo de 12 segundos?

t1= 3s                           n1= 100                           t2= 12sn2 = √K · n1                  K= 12/3=4n2 = √4 · 100 = 200

Ejemplos de programas

Si nos fijamos hasta ahora solo hemos visto bucles y bucles anidados, los bucles en si son los que determinan la complejidad que tendrá un algoritmo. Supongamos que tenemos la siguiente clase:

public class Algorithms {private static final long SLEEP_TIME = 5;public static void doNothing() {    try {        Thread.sleep(SLEEP_TIME);    } catch (InterruptedException e) {        e.printStackTrace();    }}public void linear(int endN) {    for (int i = 0; i < endN; i++)        doNothing();}public void cuadratica(int endN) {    for (int i = 0; i < endN; i++)        for (int j = 0; j < endN; j++)            doNothing();}public void cubica(int endN) {    for (int i = 0; i < endN; i++)        for (int j = 0; j < endN; j++)            for (int k = 0; k < endN; k++)                doNothing();}public void logaritmico(int endN) {    for (int i = 1; i <= endN; i *= 2) {        doNothing();    }    }}

Si nos fijamos tenemos serie de métodos que muestran las complejidades más típicas y luego un método doNothing() que básicamente lo que hace es "dormir" la ejecución del hilo principal durante SLEEP_TIME t tiempos.

Hasta aquí el artículo de hoy en el que hemos introducido de una manera muy básica la algoritmia, en los siguientes artículos miraremos como realmente estos métodos se ajustan a la curva que hemos predicho que se ajustarán. Como siempre aquí tenéis el código.

Para ti
Queremos saber tu opinión. ¡Comenta!