Análisis de algoritmos

[pic 1]

ANALISIS DE ALGORITMOS

TAREA 4

[pic 2][pic 3]

 ALGORITMO DE ORDENAMIENTO DE BURBUJA

Este algoritmo permite organizar un arreglo de dimensión n de forma ascendente o descendente. Permite organizar los valores introducidos previamente en el arreglo.

Consiste en comparar n veces todos los elementos por lo que se requiere un ciclo for con n iteraciones y un ciclo for con n-1 iteraciones.

El primer ciclo for permite hacer que todos los elementos sean movidos si es necesario

El segundo ciclo for permite hacer que se haga comparaciones entre el dato en posición a y el a+1.

Dependiendo de la forma de organizar, si se cumple que  a < a+1 se intercambian los valores con el apoyo de una variable temporal, si no, no se entra al condicional

PEOR CASO EN COMPLEJIDAD ALGORITMICA

Este se refiere al caso donde el algoritmo tendrá que realizar todas las instrucciones en todas las ocasiones en las que en lo indique. El peor caso es factible en un algoritmo con sentencias while, do while for y if. Esto se debe a que antes de realizar una instrucción, se debe cumplir una condición que dependiendo del algoritmo, será cumplida o no.

MEJOR CASO

En este caso el algoritmo cumple con las condiciones necesarias para NO ejecutar todas las instrucciones en un número de iteraciones N. Se le llama mejor caso, porque el algoritmo ya no puede ejecutar menos tareas que las que se hacen en este “mejor caso”

CASO PROMEDIO

Este caso se refiere al número de iteraciones que debe hacer un algoritmo para realizar su tarea, y que dichas iteraciones no son ni las del mejor caso, ni las del peor caso. Puede obtenerse al integrar la función de pero caso, ya que todo lo inmerso en él, son los casos intermedios.

DESARROLLO

Para analizar este algoritmo se realizará el ordenamiento de un arreglo de n = 10000 y se tomará el tiempo de ejecución.

En primer lugar se harán pruebas en el mejor caso, es decir para lograr esta ejecución los n valores del arreglo serán iguales a 1, por lo que nunca se podrá cumplir el condicionante y se podrá mejorar el tiempo de procesamiento.

También se realizarán pruebas con el caso promedio en la que los primeros 250  datos serán iguales a 2, los segundos 250  datos serán iguales a 3, los siguientes 250   a 4 y los últimos 250  a 5.

Esto provocará que la ejecución no sea la peor, pero tampoco la mejor.

Por último se realizarán pruebas con números aleatorios en los que se espera la peor ejecución, ya que en la mayoría de los casos ´se cumplirá el condicional.

Algoritmo mejor caso

[pic 4]

En este, que es el mejor caso, la ejecución del programa fue lo más rápida, ya que todos los valores a ordenar son iguales (1) por lo que nunca se entró en el condicionante para intercambiar los valores de posición.

Función de complejidad: 10n2 -4n -2

Algoritmo peor caso

[pic 5]

En este, que es el peor caso, la ejecución del programa llegó realizar todas las iteraciones que puede hacer, ya que los números que componen al arreglo fueron aleatorios yendo desde el 0 al 30.

Función de complejidad: 42n2-14n-7

Caso promedio

[pic 6]

En este caso, los números fueron introducidos de forma ordenada, los primeros 2500 eran 0, los siguientes 2500 iguales a 3, posteriormente los 2500 iguales a 2 y por último 2500 números iguales a 1.

Dado que solo el 25% de las ocasiones se intercambiarán posiciones, el caso promedio está dado por el 25% de las instrucciones dentro del condicional, por la función de complejidad generada por los ciclos for.

...