Este post continua con el problema planteado en este post. Habiendo ya analizado la complejidad de la solución básica , el siguiente paso es tratar de mejorarla proponiendo diferentes estructuras de datos para la función esta_en_lista().

Usar un array

La solución mas inmediata es cambiar la lista pasados por un array. Esta version se puede ver en solucion-array.c.

La gran diferencia entre ambas versiones es la función esta_en_lista(), que ahora nos queda:


int esta_en_lista(int value, char pasados[ MAXINT ]) {	

	if( pasados[value] == 1) return 1;
	pasados[value] = 1;
	return -1;

}

Código en solucion-array.c

Porque es una mejora?

El acceso a un array es siempre O(1). Por consiguiente el costo total del algoritmo seria O(n) * O(1), que es equivalente a O(n).

Cuales son las desventajas?

La desventaja principal es que lo que ganamos en la mejora de la complejidad de la función, lo perdemos en la complejidad espacial. Basicamente porque ahora necesitamos alocar e inicializar memoria para un array del tamaño del mayor int posible en la lista.

La otra desventaja es que es necesario inicializar el array a 0. Lo cual hace que el algoritmo de por si tenga una cota minima de O( MAXINT ), en el caso (esperable) de que la lista sea de tamaño mayor que el MAXINT posible este no es un problema ya que la porción del algoritmo que es O(n) es mayor que el MAXINT, pero si estuvieramos trabajando con un input de listas chicas, la solución anterior podria ser preferible.

En definitiva, esta solución es mas efectiva cuando el mayor int posible es pequeño y la lista es muy larga.

Usar un Binary Search Tree

Esta versión se puede ver en solucion-binary-search-tree.c. El código nos queda:


int esta_en_lista(int value, BSTree *pasados) {	
  BSTree cursor = *pasados;

  //El nodo esta vacio
  if( cursor == NULL) {
    BSTree temp = (BSTree) malloc(sizeof(struct BST_Node));
    temp->value = value;
    temp->right = NULL;
    temp->left = NULL;
    *pasados = temp;
    return -1;
  }

  //El nodo tiene el mismo valor
  if( cursor->value == value ) return 1;

  if( cursor->value < value) {
      //Fijarse en el nodo derecho
      return esta_en_lista(value, &(cursor->right));
   } else {
      //Fijarse en el nodo izquierdo
      return esta_en_lista(value, &(cursor->left));
   }
}

La ventaja inmediata de un Binary Search Tree es que la inserción y la busqueda tienen para un input promedio, complejidad O(log(n)). Esto nos mejoraría el algoritmo, llevandolo a O(n log(n)).

Sigue existiendo, sin embargo, el problema de que en el peor caso posible de una lista ordenada ascendentemente: [1,2,3,4,..]; el binary search tree se comporta exactamente igual que una lista. Esto se puede arreglar usando un Balanced Binary Search Tree, aunque es una estructura de datos un poco compleja para acordarse de su implementación y codificarla en una entrevista.

Soluciones esotéricas

Usar un bit array

Si se quiere tener una performance similar a la de un array pero con un uso menor de memoria, se puede usar un Bit Array, aunque tampoco escala bien a nivel espacio.

Usar un hashtable de binary trees

Esta es la ultima opción que codifique y se puede encontrar en solucion-hashtable-de-binary-search-trees.c. Analizar las ventajas y desventajas de esta solución se las dejo al lector.

Referencias

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

Introduction to Algorithms, 2nd Edition; Cormen, Leierson, Rivest, Stein; MIT Press; 2009