Clases de Complejidad, parte I

Como se mencionó en la sesión anterior, para comprender la teoría de complejidad parametrizada hay que tener bases de la teoría de complejidad computacional clásica, en la sesión pasada, se introdujo al lector en el tema, en esta sesión se profundizará en los parámetros que definen una clase de complejidad. Empezaremos por abordar como definir funciones para acotar el recurso que se desea medir.


Análisis de Algoritmos
La teoría de complejidad estudia la cantidad de recursos (tiempo de cómputo y el espacio en memoria) utilizados para resolver un problema, ahora bien, las preguntas son: ¿Cómo medir esos recursos?, ¿Cuál es el tiempo máximo que debo esperar para tener la solución a un problema?. Nos enfocaremos a describir como estimar teóricamente el tiempo que necesita un algoritmo para resolver el problema.

Cantidad de trabajo realizado

Típicamente se mide la eficiencia computacional de un algoritmo como el número de operaciones básicas que realiza en función del tamaño de la entrada. Generalmente para analizar un algoritmo se aisla una operación especifica que sea fundamental para el problema que se estudia. Por ejemplo, para el problema de ordenar un arreglo, las operaciones básicas serían las comparaciones. En medida que las operaciones basicas se eligan bien se tendrá una buena medida del trabajo realizado.

Ahora bien la cantidad de trabajo realizado no se puede describir solo con un número porque el número de pasos no es el mismo con todas las entradas, por esto queda claro que la medida esta en función de tamaño de la entrada y además de la "naturaleza de la entrada", por ejemplo un algoritmo para ordenar números, podría efectuar poco trabajo si esos números estan parcialmente ordenados en comparacion si estan totalmente desordenados que sería el peor caso. Casi siempre se describe el comportamiento de un algoritmo dando su complejidad del peor caso. Tenemos entonces que: "La complejidad el peor caso es el número máximo de operaciones básicas que el algoritmo ejecuta con cualquier entrada de tamaño n"

Al asociar una unidad de tiempo a cada operación básica, se tendrá el tiempo de computo T(n) y es de interes particular calcular su "complejidad" en sentido asintótico, es decir, para un tamaño de entrada suficientemente grande cuando n tiende a infinito.

Comportamiento asintótico

Cuando se estudia el comportamiento asintotico, se estudia la velocidad de crecimiento de T(n) conforme el tamaño de la entrada (instancia) aumenta. Para ello se asocia a T(n) funciones f(n ) que caracterizan su comportamiento. Es de interés en esta parte hablar de la notación O (O grande).

Definición 1 Sean f(n) y g(n) funciones de N a R:

(a) f(n) = O(g(n)) si existe una constante c > 0 tal que para una número grande de n, f(n) <=cg(n). Se tiene entonces que g(n) es una cota superior.

(b) f(n) = Omega(g(n)) si existe una constante c > 0 tal que para una número grande de n, f(n) >=cg(n). Se tiene entonces que g(n) es una cota inferior.

(c) f(n) = Theta(g(n)) si existe una constante c > 0 tal que para una número grande de n, f(n) =O(g(n)) y f(n) = Omega(g(n))

Por lo tanto la notación O(f(n)) nos dice que el tiempo de computo de un algoritmo esta a lo más caracterizado por f(n), y esta es la cota que nos interesa estudiar cuando se habla de complejidad computacional. Siempre se preferiran funciones polinomicas o de orden inferior a funciones exponenciales o factoriales. Para tener una idea clara de esto se presenta la siguiente tabla, donde Funcion, se refiere a la funcion del tiempo en segundos.

Tamaño de la entrada n
Función	10	100	1000
n	10	100	1000
n log n	33	664	9966
n^3	1000	1000000	10^9
10^6 * n^8	10^14	10^22	10^30
2^n	1024	1.27 x 10 ^30	1.05 X 10 ^301
n ^(log n)	2099	1.39 X 10^13	7.89 x 10 ^29
n!	3,628,800	10^158	4 X 10 ^2567

Dejo al lector, realizar las conversiones a minutos, días y años, ponga atención al tiempo que se llevaría resolver un problema con un algoritmo que tienen comportamiento exponencial O(2^n). Algunas lecturas recomendadas para profundizar en el tema son:

[1] Baase, Sara. Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley.
[2] Johnsonbaugh, Richard. Discrete Mathematics . Prentice Hall.

En la parte 2 de este tema abordaremos los modelos de computo y el modo de hacer computo, para en la parte 3, empezar a definir clases de complejidad y posteriormente definir términos de complejidad parametrizada.