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.

...