Análisis Algoritmico

[pic 1]

[pic 2]

Indice:

Análisis Algoritmico:

El análisis algorítmico generaliza la cantidad de operaciones que necesita un determinado algoritmo para encontrar la solución a un problema. Su uso nos permite determinar distintos tiempos de respuesta (conocidos como runtime), y determinar recursos computacionales. Una característica básica de un algoritmo es que sea correcto, produciendo el resultado deseado en tiempo finito. Debe ser claro, bien estructurado, fácil de usar y eficiente.

Para realizar el análisis de un algoritmo, debemos conocer la dificultad del problema a resolver, la dimensión de entrada, y determinar la cantidad de operaciones a realizar. La complejidad de los algoritmos puede verse reflejada en distintas funciones matemáticas, como logaritmos o exponentes. Se pueden obtener distintas funciones que logren representar un número de operaciones, independientemente de cómo se implementaron. Coincidimos en que el hecho de buscar algoritmos correctos que sean lo más eficientes posible es lo más conveniente.

Creemos que buscar algoritmos correctos que mantengan tan bajo como sea posible el consumo de recursos que hacen del sistema es lo más conveniente. Cabe recalcar que el concepto de eficiencia de un algoritmo podría ser un concepto relativo, ya que ante dos algoritmos correctos que resuelven el mismo problema, uno es más eficiente que otro si consume menos recursos. Podemos observar que el concepto de eficiencia nos permite comparar distintos algoritmos entre ellos.

Algoritmo de ordenamiento:

Un algoritmo de ordenamiento introduce elementos de una lista o un vector en una secuencia dada por una relación de orden.  Desde los comienzos de la computación, el problema del ordenamiento ha sido continuamente investigada, pudiendo deberse a la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y familiar. Aunque muchos puedan considerarlo un problema resuelto, nuevos y útiles algoritmos de ordenamiento se siguen inventando hasta el día de hoy.

Los algoritmos de ordenamiento son comunes en la introducción a la computación, donde se dan muchos conceptos base de los algoritmos, como notación de O mayúscula, estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores.

La complejidad está determinada por una cantidad de comparaciones y asignaciones entre elementos del conjunto que se realiza en una implementación específica del algoritmo. Por ejemplo, en el algoritmo de Inserción directa el caso mejor se presenta cuando el conjunto de elementos a ordenar se encuentra ya ordenado. En ese caso, los valores que se representan son los siguientes:

C_ {min}=n-1

M_ {min}=2(n-1)

C_{min} y M_{min}} son el número mínimo de comparaciones y el número mínimo de movimientos entre elementos del conjunto de datos del algoritmo de Inserción directa.

Metodos de ordenamiento:

1. Intercambio o burbuja mejorada.

Consiste en comparar pares de elementos de un vector de forma adyacente en un ciclo hasta que el arreglo esté ordenado

1. Inserción o método de la baraja.

Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian.

1. Selección o método sencillo.

El método de selección se define por buscar el elemento de menor valor del arreglo e intercambiarlo por el primero, buscar el segundo e intercambiarlo por el segundo menor valor, continuando hasta que no haya un valor mayor.

...