Complejidad

Jerarquía de Ordenes de Complejidad

• O(1): Complejidad constante. Cuando las instrucciones se ejecutan una vez.

• O(log n): Complejidad logarítmica. Esta suele aparecer en determinados algoritmos con iteración o recursión no estructural, ejemplo la búsqueda binaria.

• O(n): Complejidad lineal. Es una complejidad buena y también muy usual. Aparece en la evaluación de bucles simples siempre que la complejidad de las instrucciones interiores sea constante.

• O(n log n): Complejidad cuasi-lineal. Se encuentra en algoritmos de tipo divide y vencerás como por ejemplo en el método de ordenación quicksort y se considera una buena complejidad. Si n se duplica, el tiempo de ejecución es ligeramente mayor del doble.

• O(n2): Complejidad cuadrática. Aparece en bucles o ciclos doblemente anidados. Si n se duplica, el tiempo de ejecución aumenta cuatro veces.

• O(n3): Complejidad cúbica. Suele darse en bucles con triple anidación. Si n se duplica, el tiempo de ejecución se multiplica por ocho. Para un valor grande de n empieza a crecer dramáticamente.

• O(na): Complejidad polinómica (a > 3). Si a crecer, la complejidad del programa es bastante mala.

• O(2n): Complejidad exponencial. No suelen ser muy útiles en la práctica por el elevadísimo tiempo de ejecución. Se dan en subprogramas recursivos que contengan dos o más llamadas internas. N

Cuotas

(Big 0)

La cota superior de un algoritmo, indica una cota o la máxima razón de crecimiento que un algoritmo puede tener. Generalmente hay que especificar si es para el mejor, peor o caso promedio.

Por ejemplo, podemos decir: “este algoritmo tiene una cota superior a su razón de crecimiento de n2 en el caso promedio”.

Se adopta una notación especial llamada O-grande (big-Oh), por ejemplo O(f(n)) para indicar que la cota superior del algoritmo es f(n). • En términos precisos, si T(n) representa el tiempo de ejecución de un algoritmo, y f(n) es alguna expresión para su cota superior, T(n) está en el conjunto O (f(n)), si existen dos constantes positivas c y n0 tales que |T(n)| ≤ c |f(n)| para todo n > n0.

Ejemplo: Consideremos el algoritmo de búsqueda secuencial para encontrar un valor especificado en un arreglo. Si el visitar y comparar contra un valor en el arreglo, requiere cs pasos, entonces en el caso promedio T(n)=cs n/2. Para todos los valores n>1 |cs n/2| ≤ cs|n|. Por lo tanto, por definición, T(n) está en O(n) para n0=1, y c=cs.

El sólo saber que algo es O(f(n)) sólo nos dice que tan mal se pueden poner las cosas. Quizás la situación no es tan mala. De la definición podemos ver que si T(n) está en O(n), también está en O(n2 ) y O(n3 ), etc. Por lo cual se trata en general de definir la mínima cota

...