Bueno, este post continua con el problema del post anterior, lo que voy a hacer en este post es analizar la Complejidad del algoritmo.

Codigo con anotaciones

Para el análisis voy a hacer algunas anotaciones sobre el código, básicamente con comentarios sobre el mismo para dividirlo en diferentes partes. El código que se va a usar en el post es el siguiente:



int esta_en_lista(int value, List *pasados) {

/* B0 */
	List rList, prev;

	rList = *pasados;
	prev = NULL;

	if(rList == NULL) {
/* /B0 */
/* B01	*/
		//Agregarlo antes
		List temp;
		temp = (List) malloc(sizeof(struct Node));
		temp->value = value;
		temp->next = *pasados;
		*pasados = temp;
		return -1;
/* /B01 */
	}

/* B1 */
	while(rList != NULL) {
/* /B1 */

/* B11 */
		if(rList->value == value) return 1;
/* /B11 */
/* B12 */
		if(rList->value > value) {
/* /B12 */
/* B121 */
			List temp;
			temp = (List) malloc(sizeof(struct Node));
			temp->value = value;
			temp->next = rList;
			if(prev==NULL) {
				*pasados = temp;
			} else {
				prev->next = temp;
			}
			return -1;
/* /B121 */
		}
/* B13 */
		prev = rList;
		rList = rList->next;
/* /B13 */
	}
/* B3 */
	//Agregarlo al final
	List temp;
	temp = (List) malloc(sizeof(struct Node));
	temp->value = value;
	temp->next = NULL;
	prev->next = temp;
	return -1;
/* B3 */
}

List * sacar_duplicados(List *lista, List *pasados) {
	//Caso Base
/* A0 */
	if( (*lista) == NULL) {
/* /A0 */
/* A01 */
		return lista;
/* /A01 */
	} else {
	//PASO INDUCTIVO
/* A1 */
		if( esta_en_lista( (*lista)->value, pasados) > 0 ) {
/* /A1 */
/* A10 */
			List next = (*lista)->next;
			free( (*lista) );
			return sacar_duplicados( &(next), pasados);
/* /A10 */
		} else {
/* A11 */
			(*lista)->next = *( sacar_duplicados( &((*lista)->next), pasados) );
			return lista;
/* /A11 */
		}
	}
}


Se ve que estan separadas en el codigo las secciones que se ejecutan independientemente. Una aclaración, jamas en la practica se hace una análisis de complejidad con el nivel de detalle que tiene este post y dudo fuertemente que fuera lo que buscaba el entrevistador (la parte intuitiva de cada caso, alcanzaria), pero ya que estoy haciendo un post y considerando que hay pocos ejemplos en castellano, lo vamos a hacer relativamente riguroso y pedagógico.

Mejores Casos

Lista vacia

Este caso es trivial, pero de todas maneras es importante marcarlo. Se llama a la función sacar_duplicados() con lista igual a NULL, se llega al caso base y se retorna NULL. No hay mucho que analizar.

Lista con todos el mismo elemento

Ej: [1,1,1,1,1,1,1,1,1 …] .

Vamos a pensarlo intuitivamente:

Básicamente lo que pasa en este caso es que en el primer llamado a sacar_duplicados(), pasados esta vacio por consiguiente en la llamada a esta_en_lista() se agrega el elemento a pasados y se devuelve -1.

Ahora, lo interesante es que en todas las sucesivas llamadas, cada vez que se llame a esta_en_lista() esta función va a iterar por pasados, encontrarlo en el primer intento y devolver 1.

Es evidente que salvo para el primer elemento de la lista, para todos los demas el código va a tardar exactamente lo mismo (O sea que las llamadas a esta funcion son O(1) ). Como la función sacar_duplicados() pasa recursivamente por cada uno de los n elementos de la lista, la complejidad en este caso para todo el algoritmo es O(n).

Pensemoslo más detalladamente. En la primer llamada se ejecutan: A0, A1, A11, B0, B01 y la llamada recursiva al siguiente elemento. En cada una de las siguientes llamadas se ejecuta: A0 + A1 + A10 + B0 + B1 + B11 y la llamada recursiva al próximo elemento. En la ultima llamada, la que se hace cuando ya se recorrio toda la lista y se pasa el ultimo nodo que es NULL se ejecutan: A0 + A01 .

Podemos establecer una relación de recurrencia para analizar el algoritmo pensando en cuantas veces se ejecuta cada una de las partes. Llamemos T(n+1) a la ultima llamada, T(n) a la ultima llamado con un elemento, T(n-1) a la anterior, hasta llegar a T(1) la primer llamada. Nos queda entonces, la siguiente ecuación:

T(n+1) = A0 + A01 + T(n)
T(n) = A0 + A1 + A10 + B0 + B1 + B11 + T(n-1)
T(n-1) = A0 + A1 + A10 + B0 + B1 + B11 + T(n-2)
...
T(2) = A0 + A1 + A10 + B0 + B1 + B11 + T(1)
T(1) =  A0 + A1 + A11 + B0 + B01

La relación de recurrencia es la que va de T(n) a T(2) ya que esta es la parte recurrente, por otro lado, se podría haber planteado todo el problema solo pensando en esto, ya que es aquí donde se hace la parte del procesamiento que crece al crecer el tamaño de la lista y como tal es la que afecta la complejidad del algoritmo.

Es evidente que de 2 a n hay n-1 llamados, entonces la relacion de recurrencia nos queda resuelta como: (n-1)(A0 + A1 + A10 + B0 + B1 + B11) . El total de toda la ecuación ( sumando T(1) y T(n+1) y llamandola f(n) ) es: f(n) = (n-1)(A0 + A1 + A10 + B0 + B1 + B11) + ( A0 + A01) + (A0 + A1 + A11 + B0 + B01) o f(n) = (n+1)(A0)+(n)(A1+B0)+(n-1)(A10+B1+B11)+A01+A11+B01 .

Es evidente que esta función crece linealmente, o sea que en este caso es O(n).

Lista ordenada descendentemente

Ej: [n, n-1, n-2, n-3, …] .

Este caso es exactamente igual al anterior con la diferencia en que en cada llamado a esta_en_lista() se encuentra que el elemento nuevo es menor a todos los elementos anteriores de pasados en la primera iteración del while y se lo agrega a la misma. De nuevo, las llamadas a esta función son O(1) y el total es O(n)

Peor Caso

Lista ordenada ascendentemente

Ej: [1,2,3,4,5,6 …]

Bueno, este caso es bastante mas interesante. Intuitivamente, en este caso en cada llamado a esta_en_lista(), el while itera por cada uno de los elementos anteriores que son menores que el nuevo elemento, hasta que se termina el while y se agrega el nuevo elemento. Claramente en cada nueva llamada a la función el numero de iteraciones crece en 1. Intuitivamente podemos pensaer que como el numero de elementos de pasados es función del tamaño de la lista, esta parte es O(n) y como en sacar_duplicados() se itera por cada uno de los elementos de la lista el algoritmo total es O(n^2).

Analizemoslo más en profundidad y hagamos la recurrencia, los casos para el T(1) y T(n+1) son iguales. Luego para cada llamado en un elemento en posicion j de la lista se ejecuta (en orden): A0 + A1 + B0 + (j-1)(B1 + B11 + B12 + B13) + B3 + A10 ( que incluye la llamada recursiva al proximo elemento). La parte a ver y que es la que cambia radicalmente en relación con los casos anteriores es (j-1)(B1 + B11 + B12 + B13), que es la porcion del codigo donde se itera por cada elemento de pasados que preexiste al elemento actual. Esta parte ya no es constante para cada llamada a esta_en_lista(), efectivamente esta parte crece (linealmente) con cada nuevo llamado y luego de un suficiente numero de llamados es donde se concentrara la mayor parte de las operaciones de la función y de todo el algoritmo. Es fácil ver que para un j lo suficientemente grande, el resto de las operaciones se vuelve despreciable en relación al tiempo que se pasa en esta parte. Por ejemplo supongamos que j=1000, nos queda: A0 + A1 + B0 + (999)(B1 + B11 + B12 + B13) + B3 + A10 .

Hagamos la relación de recurrencia:

T(n+1) = A0 + A01 + T(n)
T(n) = A0 + A1 + A10 + B0 + B3 + (n-1)(B1 + B11 + B12 + B13) + T(n-1)
T(n-1) = A0 + A1 + A10 + B0 + B3 + (n-2)(B1 + B11 + B12 + B13) + T(n-2)
...
T(2) = A0 + A1 + A10 + B0 + B3 + (1)(B1 + B11 + B12 + B13) + T(1)
T(1) =  A0 + A1 + A11 + B0 + B01

Centremonos en la parte recurrente, llamemos k a (B1 + B11 + B12 + B13), l a (A0 + A1 + A10 + B0 + B3) y z a T(1) nos queda:

T(n) = l + (n-1)k + T(n-1)
T(n-1) = l + (n-2)k + T(n-2)
...
T(2) = l + (1)k + z 

Para poder pensar la recurrencia vamos a ir asignando los valores en cada paso y tratar de ver si existe algún patrón, intentemoslo:

T(2) = l + k + z
Total = l + k + z

T(3) = l + 2k + T(2)
Total = 2l + (1 + 2)k + z


T(4) = l + 3k + T(3)
Total = 3l + (1 + 2 + 3)k + z

T(5) = l + 4k + T(3)
Total = 4l + (1 + 2 + 3 + 4)k + z

...

T(n) = (n-1)l + (1 + 2 + 3 + 4 + ... + n-1)k + z

La parte del k es simplememnte una sumatoria hasta (n-1), existe una formula bastante básica para la misma que se puede encontrar acá y existe una anecdota muy simpática sobre Gauss sobre la misma. Aplicando equivalencias de sumatoria nos queda para toda esa parte (n * (n-1))/2 = (n^2 – n)/2 = (n²)/2 – n/2.

Veamos entonces como nos queda la recurrencia total (llamando w a T(n+1)): f(n) = (n-1)l + ((n^2)/2)k – (n/2)k + z + w . Esta función es cuadratica y el algoritmo total nos queda O(n^2).

Caso Medio

Pensar sobre el caso medio es todavia mas interesante, porque antes que nada tendriamos que definir exactamente que significa el caso medio y este seria el momento en el que le preguntariamos al entrevistador sobre más precisiones para poder entender el problema. Las preguntas básicas serian:

  • El numero de int posibles es finito?
  • Cuan ordenada esta la lista?
  • Cual es la probabilidad de que que se repitan elementos?
  • Es una distribución uniforme?

Intuitivamente, cuando pense el problema originalmente, mi idea era considerando:

1. si la lista no es ordenada se puede dar que en la primera aparicion de un elemento este sea mayor a x elementos que vengan despues que fueran menores en este elemento no se tendria que iterar por todos los anteriores sino solamente por una porción de estos. Ej:

[5,1,6,3,4,2,7]

Iteraciones para cada elemento y como queda pasados:
5 : 0
[5]

1 : 0
[1,5]

6 : 2
[1,5,6]

3 : 1
[1,3,5,6]

4 : 2
[1,3,4,5,6]

2 : 1
[1,2,3,4,5,6]

7 : 6
[1,2,3,4,5,6,7]

Se ven claramente dos cosas, el numero de iteraciones no coincide directamente ni con la posición n del elemento en lista, ni con su orden dentro de pasados; lo otro es que cuando un elemento es mayor a todos los elementos anteriores, si o si, se debe iterar por todos los elementos n-1 de pasados y ahí si, el numero de iteraciones coincide con la posición n del elemento en lista (menos 1).

2. Cuando un elemento se repita, independientemente del factor de ordenamiento de la lista, solo debe iterar hasta encontrarse a si mismo dentro de la lista.

Considerando estas 2 cosas habia pensado ingenuamente en considerar arbitrariamente una constante k, llamemosla factor de atenuación por ordenamiento y otra constante l llamemosla factor de atenuación por duplicados; que combinadas darian una constante c que se podria considerar como afectando la funcion anterior quedando el algoritmo dentro de alguna funcion del tipo f(n): c * n^2; 0 < c < 1 o sea terminando en O(n^2). Especificamente porque quedaria en una funcion cuadratica, porque todos los casos en que un elemento sea mayor a todos los anteriores, si o si, la función esta_en_lista() es lineal.

El problema es que cuando me puse a pensar un poco mas sobre el problema para escribir el post, me surgieron algunas preguntas y honestamente es un problema mucho más complicado de lo que pensaba. Voy a escribir un cuarto post con algunas de las conclusiones a las que llegue, incluyendo la muy sorprendente de que si el número de ints posibles es finito y el tamaño de la lista es mayor a este numero, la función puede ser expresada como una función lineal.

Pero bueno, siendo estrictos una función lineal esta acotada por una función cuadratica y por consiguiente sigue siendo O(n^2).

Referencias

Foundations of Computer Science: C Edition; Aho, Ullman; W. H. Freeman; 1994