## 1.2 NOTACIÓN ASINTÓTICA

Concepto de Complejidad

La complejidad (o costo) de un algoritmo es una medida de la cantidad de recursos (tiempo, memoria) que el algoritmo necesita. La complejidad de un algoritmo se expresa en función del tamaño (o talla) del problema.

La función de complejidad tiene como variable independiente el tamaño del problema y sirve para medir la complejidad (espacial o temporal). Mide el tiempo/espacio relativo en función del tamaño del problema.

El comportamiento de la función determina la eficiencia. No es única para un algoritmo: depende de los datos. Para un mismo tamaño del problema, las distintas presentaciones iniciales de los datos dan lugar a distintas funciones de complejidad. Es el caso de una ordenación si los datos están todos inicialmente desordenados, parcialmente ordenados o en orden inverso.

Ejemplo: f(n)= 3n2+2n+1 , en donde n es el tamaño del problema y expresa el tiempo en unidades de tiempo.

Órdenes de Complejidad

Se dice que O(f(n)) define un "orden de complejidad". Escogeremos como representante de este orden a la función f(n) más sencilla del mismo.
Así tendremos:
O(1) orden constante
O(log n) orden logarítmico
O(n) orden lineal
O(n2) orden cuadrático
O(na) orden polinomial (a > 2)
O(an) orden exponencial (a > 2)
O(n!) orden factorial

Es más, se puede identificar una jerarquía de órdenes de complejidad que coincide con el orden de la tabla anterior; jerarquía en el sentido de que cada orden de complejidad superior tiene a los inferiores como subconjuntos. Si un algoritmo A se puede demostrar de un cierto orden O1, es cierto que también pertenece a todos los órdenes superiores; pero en la práctica lo útil es encontrar la "menor cota superior", es decir, el menor orden de complejidad que lo cubra.

La mejor técnica para diferenciar la eficiencia de los algoritmos es el estudio de los órdenes de complejidad. El orden de complejidad se expresa generalmente en términos de la cantidad de datos procesados por el programa, denominada n, que puede ser el tamaño dado o estimado.

En el análisis de algoritmos se considera usualmente el caso peor, si bien a veces conviene analizar igualmente el caso mejor y hacer alguna estimación sobre un caso promedio. Para independizarse de factores coyunturales, tales como el lenguaje de programación, la habilidad del codificador, la máquina de soporte, etc. se suele trabajar con un cálculo asintótico que indica cómo se comporta el algoritmo para datos muy grandes y salvo algún coeficiente multiplicativo. Para problemas pequeños es cierto que casi todos los algoritmos son "más o menos iguales", primando otros aspectos como esfuerzo de codificación, legibilidad, etc. Los órdenes de complejidad sólo son importantes para grandes problemas.

Notación asintótica

El interés principal del análisis de algoritmos radica en saber cómo crece el tiempo de ejecución, cuando el tamaño de la entrada crece. Esto es la eficiencia asintótica del algoritmo. Se denomina "asintótica" porque analiza el comportamiento de las funciones en el límite, es decir, su tasa de crecimiento.

La notación asintótica se describe por medio de una función cuyo dominio es los números naturales (Ν ) estimado a partir de tiempo de ejecución o de espacio de memoria de algoritmos en base a la longitud de la entrada. Se consideran las funciones asintóticamente no negativas.

La notación asintótica captura el comportamiento de la función para valores grandes de N. Las notaciones no son dependientes de los tres casos anteriormente vistos, es por eso que una notación que determine el peor caso puede estar presente en una o en todas las situaciones.

###