Complejidad y tiempo

Estructura de Datos. Algoritmos. Método burbuja

  • Enviado por: Dflores
  • Idioma: castellano
  • País: México México
  • 4 páginas

publicidad

COMPARACION DE COMPLEJIDAD Y TIEMPO EN ALGORITMOS.

Se analizara el tiempo de ejecución y el tiempo empleado por los algoritmos de inserción directa, selección directa, el método de la burbuja y el método de la burbuja mejorado, ordenando una arreglo de enteros en 3 casos: en orden ascendente (mejor caso), un orden descendente (peor caso) y un orden al azar (caso promedio).

ALGORITMOS:

- INSERCION DIRECTA:

Para x=2 hasta n (+)

Y x-1

Sw 0

Mientras (y<>0) y (sw=0)

Si A[y-1]>A[y]

AuxA[y-1]

A[y-1]A[y]

A[y]Aux

De lo contrario

Sw1

Yy-1

- SELECCIÓN DIRECTA:

Para x=1 hasta n-1 (+)

Menorx

Para y=x+1 hasta n (+)

Si A[y] <A [menor]

Menory

Si menor<>x

AuxA[x]

A[x] A[menor]

A[menor] Aux

- METODO DE LA BURBUJA:

Para i=1 hasta n-1

Para j=i+1 hasta n

Si A[i]>A[j]

AuxA[i]

A[i]A[j]

A[j]Aux

  • METODO DE LA BURBUJA MEJORADO:

Sw1

Mientras sw=1

Sw 0

Para i=1 hasta n-1 (+)

Si A[i] >A[i+1]

AuxA[i]

A[i]A[i+1]

A[i+1]Aux

COMPARACION DE COMPLEJIDADES:

ORDEN DE COMPLEJIDAD

INSERCION DIRECTA

SELECCION DIRECTA

BURBUJA

BURBUJA (MEJORADO)

MEJOR CASO

O(N)

O(N2)

O(N2)

O(N)

CASO PROMEDIO

O(N2)

O(N2)

O(N2)

O(N2)

PEOR CASO

O(N2)

O(N2)

O(N2)

O(N log N)

COTA INFERIOR DE COMPLEJIDAD

INSERCION DIRECTA

SELECCIÓN DIRECTA

BURBUJA

BURBUJA MEJORADO

(N)

(N)

(N)

(N)

ORDEN EXACTO DE COMPLEJIDAD

INSERCION DIRECTA

SELECCIÓN DIRECTA

BURBUJA

BURBUJA MEJORADO

(N2)

(N2)

(N2)

(N2)

TIEMPO EN COMPARACIONES Y ASIGNACIONES:

INSERCION DIRECTA

SELECCIÓN DIRECTA

BURBUJA

BURBUJA MEJORADO

MEJOR CASO

COM

n-1

Complejidad y tiempo

Complejidad y tiempo

n-1

ASIG

0

0

0

0

PROMEDIO

COM

DEPENDE

ASIG

PEOR CASO

COM

Complejidad y tiempo

Complejidad y tiempo

Complejidad y tiempo

Complejidad y tiempo

ASIG

Complejidad y tiempo

n-1

Complejidad y tiempo

Complejidad y tiempo

CONCLUSIONES:

No se podría decir a ciencia cierta cual es el mejor algoritmo de los tres, ya que los tres presentan desventajas con respecto a los otros algoritmos en algunos casos. Pero entre los mejores se encuentran el método de selección directa y el método de la burbuja mejorado, viendo en el mejor caso, el tiempo empleado es el mismo, en el peor caso es mejor el método de selección directa, pero en cuanto su complejidad, el método de la burbuja mejorado le lleva ventaja, ya que para ordenar en el peor de los casos su complejidad es n log n, mientras que el otro es de n2.

En el caso promedio, todos los tiempos varian, por que estos no dependen n, si no que dependen del arreglo, es decir, de la probabilidad que el siguiente numero sea menor o mayor al anterior.Complejidad y tiempo

NOMBRE:

CARRERA: LICENCIATURA EN COMPUTACION.

SEMESTRE: IV.

LUNES 10 DE MARZO DEL 2002.