laboratorio 4
-
Upload
h-fer-gualotuna -
Category
Documents
-
view
212 -
download
0
description
Transcript of laboratorio 4
-
ALGORITMOS ,11 DE MARZO 2014 1
Informe de Laboratorio # 4Analisis Promedio
Fernando GualotunaFacultad de Ingeniera en Sistemas
Escuela Politecnica [email protected]
Abstract En la siguiente trabajo se implementa un codigo en lenguaje C para determinar el tiempo que se demorauna rutina ordenacion de numeros generados randomicamente 0-500 en el peor de los casos el numero x estara en unrango de 0-501 ;Programa determina si el elemento x se encuentra o No en el Arreglo.Realizar una grafica T vs N con su respecto analisis.
Index Terms
F
1 OBJETIVO
ANalizar de forma experimental un casode comportamiento promedio.
2 ESPECIFICACION DEL PROBLEMASe L el arreglo que contiene n datos de Entrada.Encontrar la posicion de un dato x en el arregloRetorna O si x no esta en el arreglo.
3 METODOCorrer varias veces el programa de un algo-ritmo de busqueda exhaustiva de numeros deuna lista de 500 numeros elegidos al azar yluego probar buscando un valor de x de entre501 posibles valores introduciendo un codigopara cronometrar tiempos.Trazar las curvas de valor promedio; y prome-dio acumulado de 1 a 500 corridas graficandopuntos de 100 en 100.
4 OPERACION BASICAComparacion de x con el contenido de unaposicion en L.
Analisis del peor caso W(n) = n. Analisis decomportamiento promedio:
P(n) =n
i=1
p(Ii)t(Ii) (1)
En el caso que tengan todos la misma proba-bilidad:
P(n) =n
i=1
(1
n)i (2)
Suponiendo que x esa en la lista:
P(n) =1
n
ni=1
=1
n
n(n+ 1)
2=
n+ 1
2(3)
Si se considera que x No esa en la lista: In+1representa x no esta en L.Sea que la probabilidad que esa en la listap(In+1) = 1 q
P(n) =n
i=1
p(Ii)t(Ii) =n
i=1
(q
n)i + (1 q)n (4)
la probabilidad que esa en L + la probabilidadque no esa en la listaP(n) = q
n
ni=1 +(1 q)n = qnn (
n+12) + (1 q)n =
q n+12
+ (1 q)n
-
ALGORITMOS ,11 DE MARZO 2014 2
4.1 Tabla de valores
4.2 Grafica t vs n
4.3 Grafica t vs n
4.4 Grafica tiempo acumulado vs numeroejecuciones
4.5 ConclusionEl comportamiento del analisis promedio dela curva tiende a ser periodica, en unos casosel tiempo de ejecucion eran igual a 0. por talrazon fueron descartados para utilizarlos en elpromedio.
La Grafica tiempo acumulado representa unarecta, se incremeta el valor en un valor con-stante k que se incrementa con el numero deveces que se corre el programa. El procesode correr el programa 100 veces problamentese estabiliza cuya grafica se muestra, aunquedebido a que el rango es de 0 a 500; la probabil-idad que encuentre un numero es 500
501= 0.9988
es decir el 99.88 %; siendo el 0.22 % que estenumero no se encuentre.
5 CODIGO FUENTEEl codigo se encuentra en los Anexos rand1.cLos datos completos en Datos.xlsx
REFERENCES[1] Msc Hallo Francisco Algoritmos Analisis Promedio;
Teoria de Algoritmos Caso Promedio , Docente de laEscuela Politecnica Nacional