Analisis De Algoritmos

Concepto de Complejidad de Algoritmos

La mayoría de los problemas que se plantean en la actualidad se pueden resolver con algoritmos que difieren en su eficiencia. Dicha diferencia puede ser irrelevante cuando el número de datos es pequeño pero cuando la cantidad de datos es mayor la diferencia crece. Ejemplo: Suma de 4 y 10 primero números naturales.

1+2+3+4 = 10

1+2+3+4+5+6+7+8+9+10 = 55 3 3

tiempo

9 3 4*(4+1)/2 = 10

10*(10+1)/2 = 55

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 graficas de la figura 1.1.

Como se puede apreciar en las graficas, entre mayor se al número de datos mayor tiempo se aplica en las graficas a), b) y c), lo cual no ocurre con la grafica 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.

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)<=cg(n) para todo entero n>= n0. Esta definición se ilustra en la figura 1.2.

Nota: el orden de magnitud de una función es el orden del término de la función más grande respecto de n.

La notación asintótica “O” grande se utiliza para especificar una cota inferior para la velocidad de crecimiento de T(n), y significa que existe una constante c tal que T(n) es mayor o igual a c(g(n)) para un número infinito de valores n.

Regla para la notación O

Definición (O)T(n) es O(f(n)) si existen las constantes positivas c y n0 tales que n >= n0 se verifica T(n)<= cf(n).

Esta definición afirma que existe un punto inicial n0 tal que para todos los valores de n después de ese punto; el tiempo de ejecución T(n) esta acotado por algún múltiplo de f(n).

La expresión matemática de lo anterior es T(n) =O(f(n)) y el índice de crecimiento de T(n) es <= al crecimiento de f(n).

T(n) Tiempo de ejecución del algoritmo.

F(n) Tiempo al introducir los datos al algoritmo.

Complejidad en el Tiempo

Tiempo de ejecución de un algoritmo.

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 cuanta que cada instrucción requiere una unidad de tiempo, dicho tiempo se puede calcular en función de n (el numero 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. Método

...