Análisis de Algoritmos

1.-Clases de analisis de algoritmos
 
Técnicas algorítmicas
Recurrencias
Recurencias básicas
Ordenamiento
Ordenamiento por inserción
Análisis del algoritmo de ordenamiento por inserción
Ordenamiento por seleccion
Análisis del algoritmo de ordenamiento por selección
Método de la burbuja
Método Shell u ordenamiento por incrementos decrecientes
Ordenamiento por mezclas sucesivas(merge)
Método rápido (quicksort)
Rendimiento del Quicksort

2. - Actividades: Análisis de algoritmos
 
Análisis de algoritmos
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 delprograma. Ambas dependen del tipo de computador y compilador, por lo que no se estudiará aquí la eficiencia de los 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.
Laeficiencia de los algoritmos está basada en una operación característica que el algoritmo repite y que define su 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 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 decomplejidad. El orden de complejidad se expresa generalmente en té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 unalgoritmo (T(n)), por lo general viene dado en función de n, y puede expresarse 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 Ccualquiera, C*g(x) >= f(x) para todo x
g(x) domina asintóticamente a f(x), si g(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 elmismo orden O(n), ellos pueden tener diferentes tiempos de ejecución para iguales valores de n. Reglas para determinar el orden de complejidad:
1.- O(C*g) = O(g)
2.- O(f * g) = O(f) * O(g) y O(f/g) = O(f) / O(g)
3.- O(f+g) = función dominante entre O(f) y O(g)
Ejemplos: O(2456 * n) = O(n)
O((20 * n) * n) = O(20 * n) * O(n) = O(n2)
Algunas de las funciones de dominación más comunes son:
n lg...