DIRECCIÓN GENERAL DE EDUCACIÓN SUPERIOR TECNOLÓGICA.

...

La complejidad de un algoritmo o complejidad computacional, estudia los recursos y esfuerzos requeridos durante el cálculo para resolver un problema los cuales se dividen en: tiempo de ejecución y espacio en memoria. El factor tiempo, por lo general es más importante que el factor espacio, pero existen algoritmos que ofrecen el peor de los casos en un menor tiempo que el mejor de los casos, lo cual no es la mejor de las soluciones.

El factor tiempo de ejecución de un algoritmo depende de la cantidad de datos que se quieren procesar. Una forma de apreciar esto es con las cuatro curvas que se presentan en las gráficas:

[pic 5]

[pic 6]

Como se puede apreciar en las gráficas, entre mayor se al número de datos mayor tiempo se aplica en las gráficas a), b) y c), lo cual no ocurre con la gráfica d), por lo tanto, podemos deducir que una función que se acerque más al eje de las x es más constante y eficiente en el manejo de grandes cantidades de datos.

El análisis de algoritmo es una parte muy importante de la ciencia de la computación, de modo que la medida de la eficiencia de un algoritmo será uno de los factores fundamentales. Por consiguiente, es importante poder analizar los requisitos de tiempo y espacio de un algoritmo para ver si existe dentro de límites aceptables. Es difícil realizar un análisis simple de un algoritmo que determine la cantidad exacta de tiempo requerida para ejecutarlo. La primera complicación es que la cantidad exacta de tiempo dependerá de la implementación del algoritmo y de la maquina en que se ejecuta. El análisis normalmente debe ser independiente del lenguaje o máquina que se utilice para implementar el algoritmo. El análisis del algoritmo tratará de obtener el orden de magnitud de tiempo requerido para la ejecución del mismo y cada algoritmo tendrá un coste computacional diferente. La eficiencia es un criterio que se debe utilizar cuando se selecciona un algoritmo y su implementación. Existe al menos tres dificultades fundamentales que son los siguientes:

- ¿Cómo se codifican los algoritmos?

- ¿Qué computadoras utilizara?

- ¿Qué datos debe utilizar el programa?

El análisis de la eficiencia debe ser independiente de la implementación específica de la computadora y de los datos específicos que se manipulan. Pero las consideraciones de eficiencia fundamentales son: el tiempo y el espacio. La complejidad del espacio de un programa es la cantidad de memoria que se necesita para ejecutar hasta la compleción (terminación). La complejidad del tiempo de un programa es la cantidad de tiempo de computadora que se necesita para ejecutar hasta la compleción al considerar estos dos aspectos podremos tener la medida exacta de tiempo y espacio del cual necesitamos para realizar u buen análisis de algoritmos. Un algoritmo será más eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.

El tiempo de ejecución es proporcional, esto es, multiplica por una constante a alguno de los tiempos de ejecución anteriormente propuestos, además de la suma de algunos términos más pequeños. Así, un algoritmo cuyo tiempo de ejecución sea T = 3N2 + 6N se puede considerar proporcional a N2. En este caso se diría que el algoritmo es del orden de N2, y se escribe O(N2).

Aritmética de la notación O.

La notación asintótica “O” (grande) se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una función, es decir, su utilidad radica en encontrar un límite superior del tiempo de ejecución de un algoritmo buscando el peor caso.

La definición de esta notación es la siguiente:

f(n) y g(n) funciones que representan enteros no negativos a números reales. Se dice que f(n) es O(g(n)) si y solo si hay una constante real c>0 y un entero constante n0>=1 tal que f(n) para todo entero n>= n0. Esta definición se ilustra en la figura [pic 7]

Tipos de análisis de la Notación O

Peor caso (usualmente)

T(n) = Tiempo máximo necesario para un problema de tamaño n.

Caso medio (a veces)

T(n) = Tiempo esperado para un problema cualquiera de tamaño n.

- Requiere establecer una distribución estadística

Mejor caso (engañoso)

Análisis del peor caso

¿Cuál es el tiempo que necesitaría un algoritmo concreto?

- Varía en función del ordenador que utilicemos.

- Varía en función del compilador que seleccionemos.

- Puede variar en función de nuestra habilidad como programadores.

---------------------------------------------------------------

- Complejidad en el tiempo

El tiempo de ejecución de un algoritmo, se refiere a la suma de los tiempos en los que el programa tarda en ejecutar una a una todas sus instrucciones, tomando en cuenta que cada instrucción requiere una unidad de tiempo, dicho tiempo se puede calcular en función de n (el número de datos), lo que se denomina T(n)

Si hacemos un análisis de forma directa al programa para determinar el tiempo de ejecución del mismo, debemos definir el conjunto de operaciones primitivas, que son independientes del lenguaje de programación que se use. Algunas de las funciones primitivas son las siguientes:

- Asignación de un valor a una variable.

- Llamada a un método.

- Ejecución de una operación aritmética.

- Comparar dos números.

- Poner índices a un arreglo.

- Seguir una referencia de objeto.

- Retorno de un método.

En forma específica, una operación primitiva corresponde a una instrucción en el lenguaje de bajo nivel, cuyo tiempo de ejecución depende del ambiente de hardware y software, pero es constante.

Ejemplo