Page 63 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Al analizar el método de ordenación por inserción binaria se advierte la presencia de un caso anti-
natural. El método efectúa el menor número de comparaciones cuando el arreglo está totalmente
desordenado, y el máximo cuando se encuentra ordenado.

Es posible suponer que mientras en una búsqueda secuencial se necesitan K comparaciones para
insertar un elemento, en una binaria se necesita la mitad de ellas. Por lo tanto, el número de compa-
raciones promedio en este método se puede calcular así:

C = 1/2+2/2+3/2+…+(n-1) / 2 = (n*(n-1)) / 4 = (n -n) / 4.
2
Por lo tanto, el tiempo de ejecución del algoritmo sigue siendo proporcional a O(n ).
2

Método de Mezcla (Merge Sort)

Este algoritmo ordena elementos y tiene la propiedad de que el peor caso en complejidad será O (n
log n). Los elementos van a ser ordenados de forma creciente. Dados n elementos, estos se dividirán
en dos subconjuntos. Cada subconjunto será ordenado y el resultado será unido para producir una
secuencia de elementos ordenados. El algoritmo 2.5 muestra el código en C:

Algoritmo 2.5. Método de mezcla

57