Análisis de algoritmos

Análisis de algoritmos1
La eficiencia de un programa tiene dos ingredientes fundamentales: espacio y tiempo. La eficiencia en espacio es una medida de la cantidad de memoria requerida por un programa. La eficiencia en tiempo se mide en términos de la cantidad de tiempo de ejecución del programa. Ambas dependen del tipo de computador y compilador, por lo que no se estudiará aquí la eficiencia delos programas, sino la eficiencia de los algoritmos. Asimismo, este análisis dependerá de si trabajamos con máquinas de un solo procesador o de varios de ellos. Centraremos nuestra atención en los algoritmos para máquinas de un solo procesador que ejecutan una instrucción luego de otra.
La eficiencia de los algoritmos está basada en una operación característica que el algoritmo repite y que definesu complejidad en Tiempo (T(n)).
T(n) es el número de operaciones características que el algoritmo desarrolla para una entrada N dada.
El máximo tiempo de ejecución de un algoritmo para todas las instancias de tamaño N, se denomina la complejidad en tiempo para el peor caso W(n). Asimismo, la complejidad promedio en tiempo es A(n), donde pj es la probabilidad de que esta instancia ocurra.
W(n) =MAX 1 <= j <= n T j(n)
A(n) = Sumatoria con j = 1 hasta k ( pj Tj(n) )
Normalmente se tendrán muchos algoritmos diferentes para resolver un mismo problema, por lo que debe existir un criterio para seleccionar el mejor. El interés principal del análisis de algoritmos radica en saber cómo crece el tiempo de ejecución, cuando el tamaño de la entrada crece. Esto es la eficiencia asintótica delalgoritmo.
La notación asintótica se describe por medio de una función cuyo dominio es los números naturales (N). Se consideran las funciones asintóticamente no negativas.
Notación O, límite asintótico superior O(g(n)) = { f(n) / existen las constantes positivas c y no / 0 <= f(n) <= c g(n) para todo n >= no}, tanto f(n) como g(n) son de Z+ --> R+.
Ejemplo: an2 + bn + c con a > 0 tiene O(n2)
NotaciónOmega grande, sean dos funciones f(n) y g(n) de Z+ --> R+. Se dice que f(n) es omega grande de g(n) si existen las constantes positivas c y no tales que f(n) >= c g(n) para todo n >= no.
Para cualesquiera de las dos funciones f(n) y g(n) definidas anteriormente se tiene que f(n) = Omega grande( g(n) ) si y sólo si g(n) = O( f(n) ).
Notación Theta grande, sean dos funciones f(n) y g(n) de Z+ -->R+. Se dice que f(n) es theta grande de g(n) si existen las constantes positivas c1, c2 y no tales que c1 g(n) >= f(n) >= c2 g(n) para todo n >= no.
Un ejemplo de algunas de las funciones más comunes en análisis de algoritmos son:

La mejor técnica para diferenciar la eficiencia de los algoritmos es el estudio de los órdenes de complejidad. El orden de complejidad se expresa generalmente entérminos de la cantidad de datos procesados por el programa, denominada n, que puede ser el tamaño dado o estimado.
Ejemplo: Un algoritmo que procese un vector V(n) tendrá un orden de complejidad de n, ya que si n crece, en esa misma proporción crece el orden de complejidad del algoritmo.
La cantidad de tiempo de procesamiento de un algoritmo (T(n)), por lo general viene dado en función de n, y puedeexpresarse según los casos típicos de ese n, caso promedio A(n), o basándose en casos extremos no deseables, como el peor de los casos W(n).
El orden de complejidad se define como una función que domina la ecuación que expresa en forma exacta el tiempo de ejecución del programa.
g(x) domina a f(x), si dada una constante C cualquiera, C*g(x) >= f(x) para todo x
g(x) domina asintóticamente a f(x), sig(x) domina a f(x) para valores muy grandes de x.
f(n) = n2 + 5n + 100, y g(n) = n2 entonces g(n) domina a f(n)
El orden de complejidad se denota con una o mayúscula, O(g(n)) , O(n2), O(n). Un orden O(n) indica que el tiempo de ejecución decrece suavemente en proporción al decrecimiento de n. Aunque dos algoritmos tengan el mismo orden O(n), ellos pueden tener diferentes tiempos de ejecución para...