calculo del caso medio, peor, mejor de un algoritmo

Dudas e ideas sobre los distintos e infinitos (:-)) algoritmos existentes.
Responder
Mensaje
Autor
Evo_pro
Mensajes: 1
Registrado: 27/03/2013 3:44 am

calculo del caso medio, peor, mejor de un algoritmo

#1 Mensaje por Evo_pro » 27/03/2013 3:54 am

hola,

estoy haciendo un programa en c++ que te dibuja un grafica con el caso medio, peor, mejor y de orden n del algoritmo de burbuja y y busqueda secuencial.

los algoritmos los tengo echo, para dibujar las graficas con gnuplot lo manejo y recoger el timepo de uso de la cpu del algoritmo con QueryPerformanceCounter de windows.h... ara bien como saco el caso medio peor y mejor ????

saludos y gracias

Avatar de Usuario
rir3760
Mensajes: 7553
Registrado: 01/10/2004 11:00 pm
Ubicación: Mexico

#2 Mensaje por rir3760 » 27/03/2013 7:08 am

Los casos mejor, peor y promedio de un algoritmo dependen de los datos que este procese. El caso mejor resulta cuando el numero de iteraciones que debe realizar es el mínimo, el peor cuando el numero de iteraciones es el máximo y el promedio es ... el promedio (usualmente se implementa con datos aleatorios).

Tomemos como ejemplo la búsqueda secuencial mas simple, esta se realiza en un conjunto de elementos desordenados. Se compara el valor a buscar con el primer elemento, segundo, etc., esto continua hasta que se encuentre o se revisen todos:

* El mejor escenario se da cuando el elemento a buscar es el primero, el numero de operaciones es el mínimo, 1.

* El peor escenario se da cuando el elemento a buscar es el ultimo, el numero de operaciones es el máximo, N.

* El caso promedio es N/2.

Con el algoritmo BubbleSort el caso es similar, debes buscar los escenarios con el mínimo/máximo numero de operaciones.

Un saludo
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language

Responder

¿Quién está conectado?

Usuarios navegando por este Foro: Google [Bot] y 1 invitado