calculo del caso medio, peor, mejor de un algoritmo

[Evo_pro]

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

[rir3760]

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