Algoritmos Complejos

Introducción

Cuando solucionamos un problema mediante la construcción de un algoritmo, normalmente podemos atacar el problema desde distintos puntos de vista, aplicando distintas estrategias, y por tanto, llegando a soluciones algorítmicas distintas.

La complejidad algorítmica es una métrica teórica que se aplica a los algoritmos en este sentido. Es un concepto que es fundamental para todos los programadores, pero sin embargo, a menudo se desconoce por completo. El objetivo de este reporte es informar acerca de lo que es en si un algoritmo complejo y las técnicas que se utilizan para su desarrollo.

Algoritmos Complejos

Un algoritmo complejo es aquel donde se resuelve un problema a traves de arboles de desiciones. A la idea del tiempo que consume un algoritmo para resolver un problema le llamamos complejidad temporal y a la idea de la memoria que necesita el algoritmo le llamamos complejidad espacial.

La complejidad espacial, en general, tiene mucho menos interés. El tiempo es un recurso mucho más valioso que el espacio. Los algoritmos de ordenación básicos se dividen en:

*Ordenación por Inserción: En este tipo de algoritmo los elementos que van a ser ordenados son considerados uno a la vez. Cada elemento es insertado en la posición apropiada con respecto al resto de los elementos ya ordenados.

Entre estos algoritmos se encuentran el de inserción directa, shell sort, inserción binaria y hashing.

Este procedimiento recibe el arreglo de datos a ordenar a[]y altera las posiciones de sus elementos hasta dejarlos ordenados de menor amayor. N representa el número de elementos que contiene a[].

paso 1: [Para cada pos. del arreglo] For i ← 2 to N do

paso 2: [Inicializa v y j] v ← a[i] j ← i.

paso 3: [Compara v con los anteriores] While a[j-1] > v AND j>1 do

paso 4: [Recorre los datos mayores] Set a[j] ← a[j-1],

paso 5: [Decrementa j] set j ← j-1.

paso 5: [Inserta v en su posición] Set a[j] ← v.

paso 6: [Fin] End.

*Ordenación por burbuja: Consiste en evaluar pares de elementos contiguos del arreglo y si el primero es mayor que el siguiente los intercambia (los más chicos quedan abajo). Todo ésto sucede dentro de dos ciclos for que recorren el arreglo. El ciclo más interno realiza las comparaciones, y se asegura ya en la primera pasada completa que el elemento ás grande del arreglo suba a la posición más alta (ésto más adelante nos permitirá desarrollar un algorítmo mejorado del método burbuja).

*Algoritmos de ordenación por selección: Consiste en buscar el menor elemento del arreglo y colocarlo en la primera posicion.Luego se busca el segundo elemento mas pequeño del arreglo y se coloca en la segunda posicion. El proceso continua hasta que todos los elementos del arreglo han sido ordenados. El metodo se basa en los siguientes principios:

1)

...