Anlisis

y

Diseo de Algoritmos

POR

JAQUELINE GONZALEZ LPEZ

DAVID TEJEDA CESATTI

El anlisis de algoritmos tiene como objetivo establecer

propiedades sobre la eficiencia permitiendo la comparacin

entre soluciones alternativas y predecir los recursos que

usar un algoritmo o ED.

BUSQUEDA BINARIA

INTRODUCCION

Es vlido exclusivamente para datos ordenados y consiste en comparar en

primer lugar con la componente central de la lista, y si no es igual al valor

buscado se reduce el intervalo de bsqueda a la mitad derecha o izquierda

segn donde pueda encontrarse el valor a buscar. El algoritmo termina si se

encuentra el valor buscado o si el tamao del intervalo de bsqueda queda

anulado.

Este mecanismo es muy eficaz para buscar un elemento cualquiera que est en

una lista ordenada, y recibe el nombre de Bsqueda Binaria o Dicotmica cuya

resolucin se base en el algoritmo de divisiones sucesivas en mitades.

Complejidad y Eficiencia

MEJOR CASO

El elemento buscado esta en el centro. Por lo tanto, se hace una sola comparacin.

PEOR CASO

El elemento buscado esta en una esquina. Necesitando log2(n) cantidad de comparaciones.

EN PROMEDIO

Sern algo como log2(n/2)

Por lo tanto, la velocidad de ejecucin depende logartmicamente el tamao del arreglo

1

Log(n)

Log(n/2)

Complejidad Algortmica

La complejidad algortmica de la Busqueda Binaria es:

Teniendo en cuenta que:

2kN2k+1

Clasificacin

Clasificar u ordenar significa reagrupar o reorganizar un conjunto de datos en una

secuencia especfica. El proceso de clasificacin y bsqueda es una actividad muy

frecuente en nuestras vidas. Vivimos en un mundo desarrollado, automatizado, donde la

informacin representa un elemento de vital importancia.

Los elementos ordenados aparecen por doquier. Registros de una biblioteca, son tal solo

algunos ejemplos de objetos ordenados con los cuales el ser humano se encuentra

frecuentemente.

La clasificacin es una actividad fundamental. Imaginmonos un alumno que desea

encontrar un libro en una biblioteca que tiene 100000 volmenes y estos estn

desordenados o estn registrados en los ndices por orden de fecha de compra. Tambin

podemos pensar lo que ocurrira si deseamos encontrar el nmero de telfono de una

persona y la gua telefnica se encuentra ordenada por nmero.

Sea A una lista de N elementos:

A1, A2, A3, ........., An

Clasificar significa permutar estos elementos de tal forma que los mismos queden de acuerdo con un orden preestablecido.

Ascendente: A1 =An

En el procesamiento de datos, a los mtodos de ordenacin se les clasifica en dos categoras:

Categora de arreglos

Categora de archivos

Eficiencia

En la bsqueda binaria la eficiencia es logartmica porque el rango de

bsqueda se divide en dos en cada iteracin

Bsqueda sin xito

ejecucin O(logN) (demostrable)

Bsqueda con xito

Caso peor

- ejecucin O(logN) (demostrable)

Caso medio

- ejecucin O(logN) (demostrable)

SHELLSORT

INTRODUCCION

Se dice fue el primer algoritmo que mejoro de forma sustancial la

ordenacin por Insercin.

Este algoritmo fue desarrollado en 1959 por Donald Shell. Hoy en da no es

conocimos el algoritmo conocido mas rpido solo es mas largo y

complejo que la ordenacin por Inserccion.

ShellSort es una algoritmo subcuadratico que funcina bien en la practica

y es fcil de implementar. El rendimiento de ShellSort depende de gran

medida de la secuencia de incrementos en que se base.

ShellSort utiliza una secuencia h1, h2,ht, denominada secuencia de Incrementos. Cualquier secuencia de incrementos es valida con tal de

que h1=1 pero algunas selecciones son mejores que otras.

Complejidad y Eficiencia

Su implementacin original, requiere O(n2) comparaciones e intercambios

en el peor caso. Un cambio menor presentado en el libro de V. Pratt

produce una implementacin con un rendimiento de O(nlog2 n) en el

peor caso. Esto es mejor que las O(n2) comparaciones requeridas por

algoritmos simples pero peor que el ptimo O(n log n).

Aunque es fcil desarrollar un sentido intuitivo de cmo funciona este

algoritmo, es muy difcil analizar su tiempo de ejecucin.

El Shell sort es una generalizacin del ordenamiento por insercin,

teniendo en cuenta dos observaciones:

El ordenamiento por insercin es eficiente si la entrada est "casi ordenada".

El ordenamiento por insercin es ineficiente, en general, porque mueve los

valores slo una posicin cada vez.

Definiciones

Las definiciones se obtuvieron con las siguientes condiciones de entrada:

Aleatorio: Tiempo de ejecucin para 50 tiempos generados de manera aleatoria, con incrementos de 2000 en el tamao del vector.

Ordenado: Tiempo de ejecucin para 50 arreglos ordenados anticipadamente. Incrementos de 2000.

Desordenado: Tiempo de ejecucin para 50 arreglos que contienen datos ordenados de Mayor a Menor. Incrementos de 2000.

El Shell sort es una generalizacin del ordenamiento por insercin,

teniendo en cuenta dos observaciones:

El ordenamiento por insercin es eficiente si la entrada est "casi

ordenada".

El ordenamiento por insercin es ineficiente, en general, porque mueve

los valores slo una posicin cada vez.