Analisis De Algoritmos

Índice

Introducción 2

Análisis de algoritmos recursivos 2

Planteamiento 3

Recursividad 3

Merge Sort 4

Quick Sort 4

Bubble Sort 5

Teoría de Grafos 6

Conclusión 6

Bibliografía 6

Introducción

El análisis de algoritmos tiene como objetivo establecer propiedades sobre la eficiencia permitiendo la comparación entre soluciones alternativas y predecir los recursos que usara un algoritmo.

Consideremos el siguiente algoritmo para determinar el mínimo de un vector A de n elementos:

i = 0; min = 0; while (i < n) {

if (A[i] < A[min]) min = i;

++i;

}

//n = 0 y min = 0 ó

//n > 0yA[min] = minfA[i]:0 ≤ i < ng

El número de operaciones elementales (comparaciones, asignaciones, sumas, etc.) que realiza es básicamente proporcional al número n de elementos del vector A y el tiempo de ejecución será, consecuentemente, de la forma a*n+b.

La “forma” del coste a * n + b es independiente del hardware sobre el que se implementa, el sistema operativo, el lenguaje de programación, etc.; sólo las constantes a y b dependen de estos factores.

Para analizar algoritmos sólo contaremos el número de operaciones elementales, asumiendo que cada una de ellas consume una unidad de tiempo.

En general, la eficiencia de un algoritmo dependerá de cada entrada concreta, no sólo del tamaño de la entrada.

Análisis de algoritmos recursivos

El coste (en caso peor, medio, .etc.) de un algoritmo recursivo T(n) satisface, dada la naturaleza del algoritmo, una ecuación recurrente: esto es, T(n) dependerá del valor de T para tamaños menores. Frecuentemente, la recurrencia adopta una de las dos siguientes formas:

T(n) = a _ T(n * c) + g(n);

T(n) = a _ T(n=b) + g(n):

Planteamiento

Se desarrollara un sistema que utilice métodos de acomodamiento Quick Sort, Merge Sort, Burbuja, así también recursividad, Arreglos para un sistema para sacar el promedio las calificaciones de un alumno o varios.

Recursividad

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * ..., incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial.

El siguiente párrafo cuentea una función, expresada con palabras, que calcula un factorial.

"Si el número es menor que cero, se rechaza. Si no es un entero, se redondea al siguiente entero. Si el número es cero, su factorial es uno. Si el número es mayor que cero, se multiplica por él factorial del número menor inmediato."

Para calcular el factorial de cualquier número mayor que cero hay que calcular como mínimo el factorial de otro número. La función que se utiliza es la función en la que se encuentra en estos momentos, esta función debe llamarse a sí misma para el número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo de recursividad.

La recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa. Normalmente, un cálculo determinado se prestará a una técnica u otra, sólo necesita elegir el enfoque más natural o con el que se sienta más cómodo.

Claramente, esta técnica puede constituir un modo de meterse en problemas. Es fácil crear una función recursiva que no llegue a devolver nunca un resultado definitivo y no pueda llegar a un punto de finalización. Este tipo de recursividad hace que el sistema ejecute lo que se conoce como bucle "infinito".

Merge Sort

El algoritmo de ordenamiento por mezcla (Merge Sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás

Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:

Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:

Dividir la lista desordenada en dos sablistas de aproximadamente la mitad del tamaño.

Ordenar cada sablista recursivamente aplicando el ordenamiento por mezcla.

Mezclar las dos sablistas en una sola lista ordenada.

El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecución:

Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.

Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.

Quick Sort

El ordenamiento

...