PEOR CASO, MEJOR CASO

En los tres ejemplos que hemos visto hasta ahora, la complejidad del algoritmo es totalmente dependiente de la talla, pero no todos los algoritmos se comportan de igual manera frente a un problema de la misma talla.

En la mayor parte de los algoritmos, también influye el propio contenido de los datos. Es posible que para un problema determinado de tamaño n, unas veces el algoritmo tarde más y otras tarde menos, dependiendo de los propios datos de entrada del problema de tamaño n.

Un ejemplo... Éste algoritmo comprueba si un determinado valor x está contenido en un array v, cuyos índices van de 1 a n

01 funcion EstaEn(v: array[1..n] de enteros, x: entero):booleano
02 empieza
03    variables: i:entero, encontrado:booleano;
04    i=1;
05    encontrado=false;
06    mientras(NO(encontrado) Y x<=n) hacer
07       si v[i]==x entonces
08         encontrado=true;
09       fin si
10       i=i+1
11    fin mientras
12    devolver encontrado
13 termina

Contiene en su interior un bucle mientras que no se ejecuta un número determinado de veces (como ocurría en los ejemplos anteriores, que utilizaban bucles for). Imagina que pasamos a esa función un vector de n=100 enteros, y un entero x=17. Es evidente que la talla del problema es n=100, ya que es lo que determina el número de instrucciones que se ejecutarán. Sin embargo, es posible que el valor 17 esté situado en la posición 30 del vector, con lo que el bucle se realizará 30 veces, o quizá en la posición 50, o quizá no esté en el vector, con lo que el bucle se ejecutará n=100 veces, recorriendo todo el vector.

En éste caso, nos conviene distinguir dos métricas: qué es lo peor que nos puede pasar para un problema de tamaño n, y qué es lo mejor que nos puede pasar para un problema de tamaño n.

Vamos a echar unas pocas cuentas para el ejemplo de arriba. Vamos a suponer que en el interior del bucle mientras hay 2 instrucciones (el si y el incremento de i), y en el exterior hay 3, dos antes del mientras y una después.

Pues bien... lo mejor que nos puede pasar es que encontremos el valor x a la primera. En ese caso, el bucle se ejecuta una sola vez.. El número de instrucciones que realizamos son 3+2=5.

Lo peor que puede pasar es que el valor x no se encuentre en el vector, así que el bucle se ejecutará n veces, recorriendo todo el vector. El número de instrucciones que realizamos es 3+2n

Para expresar esto, se utiliza una notación específica, diremos que para este algoritmo, su complejidad en el peor caso es O(2n+3) A esta notación se le denomina "O Grande" (del inglés "Big-O"), o simplemente "Complejidad en el peor caso". Aunque es una "O", realmente viene de la letra griega Omicron. Fue introducida por el matemático Paul Gustav Heinrich Bachmann.

Análogamente, diremos que para este algoritmo su complejidad en el mejor caso es Ω(5). A esta notación se le denomina "Omega" (por la letra griega omega mayúscula Ω) o simplemente, "complejidad en el mejor caso".

En general, cuando decimos "complejidad" a secas, casi siempre nos referimos a la complejidad en el peor caso. Es decir... cuánto va a tardar el algoritmo como mucho.