Instinto Lógico

Recuerda que nadie debe pensar por tí.

Complejidad computacional

complejidad computacionalEl primer paso para resolver un problema informático es encontrar un algoritmo que lo resuelva. Pero una vez resuelto el problema, nos surgen las siguientes dudas: ¿Exisiten algoritmos “mejores” para resolver el problema?

Podríamos decir que algoritmo, es una sucesión finita de operaciones elementales, que sabemos ejecutar cuando actua sobre una serie de datos. Un algoritmo, será mejor que otro en tiempo si, actuando sobre los mismos datos, el tiempo de ejecución es menor, y será mejor que otro en espacio si, actuando sobre los mismos datos, la memoria, principal o secundaria, que utilza es menor. Pero, tanto el tiempo como el espacio utilizado dependen de la máquina en la que ejecutemos el algoritmo, por tanto hay que determinar una forma para estudiar la eficiencia de los algoritmos independiente de la máquina que se utilice.

Tenemos que encontrar una forma para evaluar algoritmos independiente de al máquina en la que se ejecuten, así que lo que haremos será contar el número de operaciones que realiza un programa.

Supongamos que tenemos dos algoritmos A1 y A2 para resolver un determinado problema. Cuando los algoritomos anteriores, actúan sobre n datos se tiene que A1 hace S1 sumas, P1 productos y C1 comparaciones, y A2 realiza S2 sumas, P2 productos y C2 comparaciones siendo:

A1 A2
S1=n5+46n3 S2=23n2
P1=n2+37n P2=n3+456n2
C1=45n C2=n4+86n

Y ahora nos preguntamos ¿Qué algoritmo es mejor?

Habrá que ver cuantos datos elementales tenemos y sustituir en cada una de las expresiones, de esta forma veremos qué algoritmo hace más operaciones, pero interesa saber qué algoritmo es mejor cuando n es grande, si n es pequeño no habrá diferencias sustanciales.

Obviamente, cuando n tienda a infinito el algoritmo A1 utilizará casi todo el tiempo en realizar sumas, mientras que A2 lo utilizara en realizar comparaciones. Por tanto, si n tiende a infinito, A1 tenderá a infinito como n5 y A2 tenderá a infinito como n4, por lo que podemos afirmar que A2 es más rapido que A1 salvo posiblemente para un número finito de datos. Diremos que A1 tiene una complejidad de orden n5 (lo denotaremos O(n5))y A2 tiene una complejidad de n4 (lo denotaremos O(n4)).

Así pues, para calcular la complejidad computacional de un algorimo, no hay que programarlo al detalle, basta con ver cuantas veces se realiza la operación que más se repite.

Veamos la importancia de la complejidad comutacional con un ejemplo.

CÁLCULO DEL DETERMINANTE DE UNA MATRIZ.

Vamos a calcular la complejidad computacional del cálculo del determinante de una matriz por dos métodos.:

  • Calculo del determinante de una matriz por menores.
  • Calculo del determinante de una matriz triangulando y multipilcando la diagonal.

Para calcular la complejidad asintótica de un algoritmo no hace falta programarlo al detalle, basta con evaluar la operación que más veces se repite.

Para calcular el determinante de una matriz n x n, tenemos la media natural del tamaño del problema que es n, veamos cual es la complejidad si utilizamos el método de los menores.

En este método:

|A|=a11A11 + a21A21+ ….+an1An1

Siendo |A| la matriz inicial de elementos aij, y Aij el adjunto de aijcuyo cálculo se deduce al de un determinante de (n-1) x (n-1)

Si denotamos por P(n) y S(n) el número de productos y sumas necsarios para calcular |A| por este método tenemos:

(1)  P(n)=n+nP(n-1)

(2) S(n)=n-1 +nS(n-1)

Además P(1)=S(1)=0.

Para conocer la complejidad basta con saber el orden de la magnitud de P(n)

De (1) dividiendo por n! y simplificando n obtenemos

P(n)/n!=P(n-1)/(n-1)!+1/(n-1)! => (reiterando la igualdad) => P(n)/n!=1 + 1/2! + 1/3!+ ….+1/(n-1)! ~ e-1

Por tanto P(n) ~ (e-1)n! => P(n) es O(n!)

Análogamente de 2 se obtiene S(n)~ n!-1

Si quiseramos calcular el determinante de una matriz 30×30 el número de productos necesarios sería aproximadamente:

(e-1)30! ~ (e-1)3030 *e-30(60π)1/2~ 10 32 tente) necesitaría  1010 siglos sólo para calcular los productos!!!

Ahora veamos el método de la triangulación:

|A|=a11|A’| siendo A’ la matriz de (n-1) x (n-1) elementos a’ij=aij-ai1/a11 (suponiendo a11 !=0)  i=2, …., n ; j= 2, …., n;

Para calcular |A’| utilizamos el mismo método. Si encontramos a11=0 intercambiamos la primera columna por otra cuyo primer elemento se no nulo, el determinante sigue siendo el mismo salvo quizás el signo. Si todas las columas tienen su primer elemento a 0 el determinante también es 0

Denotamos P(n), S(n) y D(n) el número de productos sumas y divisiones que debemos realizar para calcular un determinante no nulo.

(1) P(n)=(n-1)(n-1) + 1 + P(n-1)

(2) S(n)=(n-1)(n-1) + S(n-1)

(3) D(n)=(n-1) + D(n-1)

Además P(1)=S(1)=D(1)=0

Para calcular la complejidad basta con calcular P(n)

P(n)=(n-1)2 + 1 + P(n-1) = (n-1)2 + 1 + (n-2)2+1+ P(n-2)= —= n – 1 + (1 + 22 + 32 + ….. +n2)

Por lo que P(n)=(n-1)n(2n-1)/6 => P(n) es O(n3)

Y calcular una matriz 30 x 30 nos costaría menos de un segundo

 

Be Sociable, Share!

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Instinto Lógico © 2014 Frontier Theme