Materia: #algoritmos_y_estructuras_de_datos

Complejidad

A la hora de diseñar algoritmos y estructuras de datos, tenemos que procurar dos cosas clave: que el algoritmo en cuestión efectivamente resuelva el problema (lo que venimos viendo hasta ahora); y que sea eficiente. Ahora bien, ¿Qué significa la $e f i c i e n c i a$ ?

Si tuviéramos dos algoritmos, y uno tarda 2 horas, y el otro tardase 1 hora, es fácil advertir cual de los dos es mejor: el segundo. Tarda menos, evidentemente lo que sea que haga lo hace $m e j o r$ .

Supongamos que tenemos un programa, y nos interesa determinar su duración en base al tamaño del input. Es decir, queremos ver la relación entre el tamaño de la entrada (por ejemplo, que tan larga es una lista de entrada) y el tiempo que consume resolver el problema (por ejemplo, cuanto tarda en encontrar un elemento en esa lista). Este concepto de relación entre el tamaño de la entrada y el tiempo que consume, es al que llamamos eficiencia. A mayor eficiencia, menor tiempo consumirá con inputs grandes.

En el ejemplo hablamos de la duración temporal del programa, pero podríamos estar buscando reducir otra cosa (tamaño en memoria, consumo de energía, entre otras particularidades).

Esta medida de la eficiencia es la que nos va a permitir elegir entre dos o mas algoritmos, poder categorizarlos y evaluarlos, determinar cual es mejor o peor que otro según la circunstancia que queramos medir.

Ahora bien, medir el tiempo de un programa no es tarea fácil. Uno puede hacerlo de dos maneras: midiéndolo a mano, es decir, cronometrando el programa al correrlo; o medirlo de manera teórica en base a su comportamiento. La primera medida tiene varios posibles contratiempos. A saber, quizás cambie la medición según la computadora que corre el programa, siendo una mas potente que la otra, o quizás depende del lenguaje en el que este escrito pero no del algoritmo en si. La segunda medida, por otro lado, es independiente a la computadora o al lenguaje, y vale para cualquier instancia del programa.

Vamos a basarnos en un concepto importante para medir la complejidad: las operaciones elementales ( $O E$ ). Estas van a ser instrucciones que vamos a considerar con tiempo 1 (no tiene unidad definida). El tiempo de un programa, entonces, será la suma de tiempos de cada instrucción.

Un poco de notación: vamos a llamar $T (n)$ a la complejidad temporal para un tamaño de entrada $n$ , y por otro lado, $S (n)$ denotará la complejidad espacial para un tamaño de entrada $n$ . Finalmente, llamaremos $t (S)$ al tiempo que tarde en ejecutar el programa $S$ .

De lo anterior se deducen las siguientes reglas:

$t ($ If C Then S1 Else S2 Endif; $) = t (C) + m a x {t (S 1); t (S 2)}$
$t ($ Case C Of v1:S1 | v2:S2 | …| vn:Sn End; $) = t (C) + m a x {t (S 1); t (S 2), . . ., t (S n)}$
$t ($ While C Do S End; $) = t (C) + (cantidad de iteraciones) \times (t (C) + t (S))$
$t ($ MiFuncion(P1, P2, …, Pn) $) = 1 + t (P 1) + t (P 2) + . . . + t (P n) + t (F)$

En el ultimo caso tenemos una llamada a función, donde toma n parámetros, y hace la operación F.

Hay que tener una cosa mas en cuenta: entradas de mismo tamaño pueden tener medidas de tiempo diferentes. Por ejemplo, supongamos que queremos evaluar la complejidad de un algoritmo que busca un elemento en una lista, y lo que hace es chequear uno a uno entre los elementos y compararlos con el elemento en cuestión. Si la lista es mas larga, el algoritmo llevara mas tiempo en resolverse, salvo que el elemento este al principio de la lista. Es decir, si preguntamos por el primer elemento de la lista, por mas larga que esta sea, vamos a medir siempre el mismo tiempo (el mínimo, en este caso).

Es por esta situación que nos interesan tres casos particulares de la medición del tiempo: el caso peor, el caso mejor y el caso medio. Podemos construirlos de la siguiente manera:

$T_{p e o r} (n) = m a x_{i n s t a n c i a s I, | I | = n} {t (I)}$
$T_{m e j o r} (n) = m i n_{i n s t a n c i a s I, | I | = n} {t (I)}$
$T_{p r o m e d i o} (n) = \sum_{i n s t a n c i a s I, | I | = n} {P (I) \times t (I)}$

$P (I)$ en este contexto representa la probabilidad de que un input sea la instancia $I$ .

Análisis asintótico de la complejidad

En general, no nos interesa saber el tiempo exacto de un algoritmo, sino que nos interesa ver su crecimiento. Es decir, nos interesa su orden de magnitud. De esa forma, vamos a poder evaluar mas fácilmente entre dos algoritmos que, a priori, tienen medidas distintas, pero quizás mismo orden de magnitud, o viceversa.

Entonces, decimos que el orden (logarítmico, lineal, cuadrático, exponencial, etc.) de la función $T (n)$ es el que expresa el comportamiento dominante cuando el tamaño de la entrada es grande. En otras palabras, es lo que nos interesa realmente.

Como tal, lo que nos interesa es el análisis asintótico de la complejidad, que es el comportamiento de la misma para valores de entrada suficientemente grandes. Nosotros vamos a aproximar estos valores con cotas (de ahí lo asintótico), las cuales denotamos:

$O$ (O grande) es la corta superior
$Ω$ (omega) es la corta inferior
$Θ$ (theta) es el orden exacto de la función

Estas cotas van a determinar los limites de la complejidad del algoritmo que estemos analizando. La notación $f \in O (g)$ indica que la función $f$ no crece más rápido que alguna función proporcional a $g$ . Estamos diciendo que $O (g)$ es un conjunto de funciones, y lo definimos como:

O (g) = {f | \exists n_{0}, k > 0 tal que n \geq n_{0} ⟹ f (n) \leq k \cdot g (n)}

Análogamente, definimos a omega como:

Ω (g) = {f | \exists n_{0}, k > 0 tal que n \geq n_{0} ⟹ f (n) \geq k \cdot g (n)}

Finalmente, a theta lo expresamos así:

Θ (g) = {f | \exists n_{0}, k_{1}, k_{2} > 0 tal que n \geq n_{0} ⟹ k_{1} \cdot g (n) \leq f (n) \leq k_{2} \cdot g (n)}

Una vez explicadas estas definiciones podemos empezar a deducir muchas de las propiedades que vamos a utilizar a la hora de resolver ejercicios de complejidad. Aca listamos unas cuantas:

Si existe $lim_{n \to 1} \frac{f (x)}{g (x)} = k$ , y segun los valores de $k$ :
- Si $k \neq 0$ y $k < \infty$ , entonces $Ω (f) = Ω (g)$ , $Θ (f) = Θ (g)$ y $O (f) = O (g)$
- Si $k = 0$ , entonces $Ω (f) \neq Ω (g)$ , $Θ (f) \neq Θ (g)$ y $O (f) \neq O (g)$
Si $f_{1} \in O (g)$ y $f_{2} \in O (h) ⟹ f_{1} + f_{2} \in O (m a x {g, h})$
Si $f_{1} \in O (g)$ y $f_{2} \in O (h) ⟹ f_{1} \cdot f_{2} \in O (g \cdot h)$
Si $f_{1} \in Ω (g)$ y $f_{2} \in Ω (h) ⟹ f_{1} + f_{2} \in Ω (g + h)$
Si $f_{1} \in Ω (g)$ y $f_{2} \in Ω (h) ⟹ f_{1} \cdot f_{2} \in Ω (g \cdot h)$
Si $f_{1} \in Θ (g)$ y $f_{2} \in Θ (h) ⟹ f_{1} + f_{2} \in Θ (g + h)$
Si $f_{1} \in Θ (g)$ y $f_{2} \in Θ (h) ⟹ f_{1} \cdot f_{2} \in Θ (g \cdot h)$

Existen muchas propiedades mas, pero estas suelen ser las mas utiles.

Ahora, ¿como se relaciona todo esto con la eficiencia de programas? Bueno, ahi es donde entra lo que definimos antes de la función $T (n)$ . Vamos a analizar estas funciones temporales en base a estas cotas, utilizando la notación antes mostrada. A saber, si tenemos que:

T_{p e o r} \in O (g)

Decimos que el peor de los casos (la peor instancia de un tamaño $n$ ), la función temporal $T (n)$ no va a superar a $g (n)$ . Es decir, es su cota superior. Podríamos hacer análisis similares con las distintas cotas, son bastante análogas. También, podemos utilizar lo que vimos antes de los casos peor, mejor y promedio.

Vamos a mencionar casos conocidos o que ya vimos y mostrar su correspondiente complejidad.

Para empezar, tenemos el famoso caso de buscar un elemento en una lista. Si la lista no tiene una forma de orden, nos va a ser muy dificil encontrar una forma eficiente de encontrar un elemento en ella. Lo unico que podemos hacer es ir chequeando uno a uno, y compararlo con el elemento en cuestion. En el peor de los casos, terminamos chequeando todos los elementos (o bien el elemento esta en la ultima posicion de la lista, o bien ni siquiera pertenece). Eso quiere decir que, si la lista mide $n$ , podemos decir que el algoritmo de busqueda tiene una complejidad $O (n)$ , ya que es el peor de los casos. A su vez, el mejor de los casos es que el elemento si pertenezca, y este en la primera posicion. Por lo que podemos añadir que el algoritmo tiene $Ω (1)$ .

Ahora, supongamos que la lista esta ordenada. Por ejemplo, es una lista de numeros enteros y se encuentra ordenada de menor a mayor. En este caso podriamos llegar a provecharnos de esto y usarlo a nuestro favor. No hace falta chequear uno a uno cada elemento, podriamos dividir la lista a la mitad, y ver si el elemento que estamos buscando pertenece a una o a la otra. Para hacer esto, podriamos preguntar si el elemento es mayor que el valor del medio. Al estar la lista ordenada, podemos afirmar que esto nos separa la lista en dos, y que con ese dato ya sabemos a que mitad pertenece. Noten que esto se puede hacer repetidas veces hasta llegar al elemento en cuestion (si pertenece, en caso contrario, llegariamos a un numero al que no podriamos llegar, o lista vacia). Si hacen las cuentas que ahora no vamos a detallar, podemos llegar a que, en el peor de los casos, la complejidad de este algoritmo es de $O (l o g_{2} (n))$ , lo cual es mucho mejor que $O (n)$ . A este algoritmo se le conoce como busqueda binaria.

Como veran, el simple dato de que la lista esta ordenada, ya nos ayuda a agilizar el procedimiento. El problema ahora seria procurar que la lista siempre se encuentre ordenada.

Materia: #algoritmos_y_estructuras_de_datos

Tags:

Complejidad

Análisis asintótico de la complejidad