¿Como medir la complejidad?
05 03 2008
Con este pequeño artículo trataré de explicar como es posible medir la complejidad de algo, computacionalmente hablando. Aunque ciertamente estas ideas podrían ser utilizadas en otras muchas ramas en donde se presenta un problema que debemos resolver y la eficiencia de su resolución (en tiempo) sea un parámetro importante.
La resolución práctica de un problema computacional exige por una parte un algoritmo o método de resolución y por otra un programa o codificación (implementación) de ese algoritmo en un ordenador real. El algoritmo es esencial a diferencia de la codificación que puede convertirse en anecdótica, aunque lo más normal es que no lo sea, a fin de cuentas los bugs están en la implementación y no en el algoritmo.
A efectos prácticos además hay que tomar en consideración la cantidad de recursos, tanto de tiempo como de memoria que la implementación de un algoritmo puede precisar. Este suele depender del tamaño del problema pues el algoritmo y la implementación se deban adaptar a diferentes parámetros de entrada, por ejemplo, no es lo mismo ordenar alfabéticamente un array con nombres para un tamaño de array de 100 que para otro de tamaño 100.000 tanto en tiempo como en memoria empleada. El concepto exacto que mide el tamaño del problema depende de la lógica del mismo y es por lo tanto imposible dar una regla para su medición.
Aunque el tamaño en memoria que una implementación pueda ocupar debe ser tomado en consideración esto ha dejado de ser problemático debido al aumento de la capacidad de memoria de los equipos y aunque puede parecer que a la capacidad de cálculo le pasa lo misma esto no es así. Y es un error común pensar que la optimización del código pueda ser dejada de lado confiando en la potencia de cálculo de nuestros equipos o de equipos futuros. Es pues el tiempo de ejecución el principal baremo a tener en cuenta a la hora de diseñar un algoritmo o afirmar que un algoritmo es "mejor" que otro.
La resolución práctica de un problema computacional exige por una parte un algoritmo o método de resolución y por otra un programa o codificación (implementación) de ese algoritmo en un ordenador real. El algoritmo es esencial a diferencia de la codificación que puede convertirse en anecdótica, aunque lo más normal es que no lo sea, a fin de cuentas los bugs están en la implementación y no en el algoritmo.
A efectos prácticos además hay que tomar en consideración la cantidad de recursos, tanto de tiempo como de memoria que la implementación de un algoritmo puede precisar. Este suele depender del tamaño del problema pues el algoritmo y la implementación se deban adaptar a diferentes parámetros de entrada, por ejemplo, no es lo mismo ordenar alfabéticamente un array con nombres para un tamaño de array de 100 que para otro de tamaño 100.000 tanto en tiempo como en memoria empleada. El concepto exacto que mide el tamaño del problema depende de la lógica del mismo y es por lo tanto imposible dar una regla para su medición.
Aunque el tamaño en memoria que una implementación pueda ocupar debe ser tomado en consideración esto ha dejado de ser problemático debido al aumento de la capacidad de memoria de los equipos y aunque puede parecer que a la capacidad de cálculo le pasa lo misma esto no es así. Y es un error común pensar que la optimización del código pueda ser dejada de lado confiando en la potencia de cálculo de nuestros equipos o de equipos futuros. Es pues el tiempo de ejecución el principal baremo a tener en cuenta a la hora de diseñar un algoritmo o afirmar que un algoritmo es "mejor" que otro.
El tiempo de ejecución
Una medida útil para conocer el tiempo de ejecución de un programa dependiendo de su tamaño (N) es lo que llamaremos a partir de ahora T(N). Para un programa del tipo
S1; for(i=0;i<N;i++) S2;
Siendo S1 y S2 un conjunto de sentencias válidas tenemos que su función T(N) tendría la forma
T(N) = T(S1) + N*T(S2)
Cualquier fórmula de T(N) hace referencia a N o/y a una serie de parámetros constantes. Dado que la potencia computacional aumenta cada año hay que analizar los algoritmos dejando de lado estos dos factores (N y parámetros constantes) haciendo que nuestro análisis sea independiente de la máquina empleada.
Para hacer esto se suele calcular el comportamiento cuando N tiende a infinito, es decir, su comportamiento asintótico. Se suele en estos caso no hablar de una función que nos da el tiempo dado el tamaño del problema sino que se suele definir un conjunto de funciones que nos dan este comportamiento y se afirma que estas funciones son del Orden de f(n) siendo esta una función representativa de todas ellas. Y se denota el orden por O(f(n)). Para caracterizar formalmente esta definición tenemos que:
en otras palabras O(f(n)) está formado por todas las funciones que crecen a un ritmo menor o igual a f(n). Es decir f(n) es la cota superior para este conjunto de funciones g(n).
O(f(n)) define un orden con todas sus propiedades, escogemos un representante de este orden y así tendremos:
O(1) orden constante
O(log n) orden logarítmico
O(n) orden lineal
O(n log n)
O(n2) orden cuadrático
O(na) orden polinomial (a > 2)
O(an) orden exponencial (a > 2)
O(n!) orden factorial
Esto nos dará pues un indicador de la bondad de un algoritmo, cuanto menor sea el orden mejor.
Para saber más:
Complejidad algorítmica
La complejidad de los algoritmos
Complejidad algoritmos
Notas sobre complejidad algorítmica
Comentarios :
No hay comentarios »
Una medida útil para conocer el tiempo de ejecución de un programa dependiendo de su tamaño (N) es lo que llamaremos a partir de ahora T(N). Para un programa del tipo
S1; for(i=0;i<N;i++) S2;
Siendo S1 y S2 un conjunto de sentencias válidas tenemos que su función T(N) tendría la forma
T(N) = T(S1) + N*T(S2)
Cualquier fórmula de T(N) hace referencia a N o/y a una serie de parámetros constantes. Dado que la potencia computacional aumenta cada año hay que analizar los algoritmos dejando de lado estos dos factores (N y parámetros constantes) haciendo que nuestro análisis sea independiente de la máquina empleada.
Para hacer esto se suele calcular el comportamiento cuando N tiende a infinito, es decir, su comportamiento asintótico. Se suele en estos caso no hablar de una función que nos da el tiempo dado el tamaño del problema sino que se suele definir un conjunto de funciones que nos dan este comportamiento y se afirma que estas funciones son del Orden de f(n) siendo esta una función representativa de todas ellas. Y se denota el orden por O(f(n)). Para caracterizar formalmente esta definición tenemos que:
O(f(n))= {g: ENTERO -> REAL+ tales que
existen las constantes k y N0 tales que
para todo N > N0, g(N) <= k*f(N) }
en otras palabras O(f(n)) está formado por todas las funciones que crecen a un ritmo menor o igual a f(n). Es decir f(n) es la cota superior para este conjunto de funciones g(n).
O(f(n)) define un orden con todas sus propiedades, escogemos un representante de este orden y así tendremos:
O(1) orden constante
O(log n) orden logarítmico
O(n) orden lineal
O(n log n)
O(n2) orden cuadrático
O(na) orden polinomial (a > 2)
O(an) orden exponencial (a > 2)
O(n!) orden factorial
Esto nos dará pues un indicador de la bondad de un algoritmo, cuanto menor sea el orden mejor.
Para saber más:
Complejidad algorítmica
La complejidad de los algoritmos
Complejidad algoritmos
Notas sobre complejidad algorítmica
Categorías : Articulos programación
Referencias : 1 Referencia »
Powered by Novanebula
Tracked: Mar 22, 19:22