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
