|
Página 6 de 8
ÓRDENES DE COMPLEJIDAD MÁS COMUNES
Como ya hemos mencionado, la complejidad, digamos "real" en el peor caso de los algoritmos puede enmarcarse en un "orden de complejidad". Dicho de otra manera, la complejidad de un algoritmo "crece como" el representante de su orden cuando la talla del problema se hace muy grande.
Bien... pues los órdenes de complejidad que se suelen manejar son éstos, de mejor a peor.
| Órden |
Nombre |
Comentario |
| O(1) |
constante |
Todos aquellos algoritmos que responden en un tiempo constante, sea cual sea la talla del problema. Son los que aplican alguna fórmula sencilla, por ejemplo, hallar el máximo de dos valores |
| O(log n) |
logarítmico |
Los que el tiempo crece con un criterio logarítmico, independientemente de cuál sea la base mientras ésta sea mayor que 1. Por eso, normalmente, ni siquiera se indica la base. No suelen ser muchos, y normalmente están bien considerados, ya que implican que un bucle realiza menos iteraciones que la talla del problema, lo cual no suele ser muy común. Por ejemplo, la búsqueda dicotómica en un vector ordenado. |
| O(n) |
lineal |
El tiempo crece linealmente con respecto a la talla. Por ejemplo, encontrar el máximo de un vector de talla n. |
| O(n log n) |
enelogarímico, loglineal, linearítmico o simplememente n por logaritmo de n |
Éste orden tiene muchos nombres. Es un orden relativamente bueno, porque la mayor parte de los algoritmos tienen un orden superior. En éste orden está, por ejemplo, el algoritmo de ordenación Quicksort, o la transformada rápida de Fourier. |
| O(nc), con c>1 |
polinómico |
Aquí están muchos de los algoritmos más comunes. Cuando c es 2 se le llama cuadrático, cuando es 3 se le llama cúbico, y en general, polinómico. Intuitivamente podríamos decir que éste órden es el último de los aceptables (siempre y cuando c sea relativamente bajo). A partir del siguiente, los algoritmos son complicados de tratar en la práctica cuando n es muy grande. |
| O(cn), con c>1 |
exponencial |
Aunque pudiera no parecerlo, es mucho peor que el anterior. Crece muchísimo más rápidamente. |
| O(n!) |
factorial |
Es el típico de aquellos algoritmos que para un problema complejo prueban todas las combinaciones posibles. |
| O(nn) |
combinatorio |
Tan intratable como el anterior. A menudo no se hace distinción entre ellos. |
Hay otros órdenes intermedios, e incluso superiores... (realmente, tantos como queramos), pero usualmente se suelen utilizar los de la tabla de arriba, que son órdenes bastante representativos.
Lo que estamos haciendo, al escoger esos órdenes es particionar todas las posibles complejidades en una serie de "clases de complejidad". Por supuesto, a su vez, cada una de esas "clases de complejidad" podría volverse a dividir en distintas subclases, pero eso puede convenirnos algunas veces y otras no es práctico, por lo menos desde una visión general. Por ejemplo, el órden exponencial contiene a O(2n) y a O(3n) y a O(4n)... etc. Lo mismo ocurre con (nc), que contiene a O(n2), y a O(n3) .... y a O(n1000)...
Para la complejidad en el mejor caso se utilizan los mismos órdenes, sólo que en lugar de utilizar la letra O (Omicron) para denotarla se utiliza Ω (Omega).
Así pues, por ejemplo, para el algoritmo de ejemplo que obtenía si un valor x estaba en un array de tamaño n, decimos que su complejidad (en el peor caso) está en el orden O(n) y (en el mejor caso) en el orden Ω(1).
|
Artículos 
