• Conocimientos mínimos: nociones básicas de complejidad
• Conocimientos recomendados: búsqueda binaria

Un problema común a enfrentar a la hora de resolver un problema es saber si un elemento está en un conjunto o no. Por ejemplo, si cierto elemento está en la lista de elementos visitados (muy útil para algoritmos como BFS o DFS) o más en general si un número se encuentra en una lista de números. Más aún, muchas veces debemos responder a esta pregunta numerosas veces durante la ejecución del programa, así que es importante que lo podamos hacer rápidamente.

Plantearemos un problema y veremos diferentes formas de resolverlo. Imaginemos que tenemos un idioma en el cual existe una lista de palabras válidas, y el resto de las palabras no lo son. Queremos hacer un programa que resuelva muy rápidamente si algunas palabras son válidas o no. Por ejemplo,

lista de palabras válidas: {casa, pato, luna, comida, la, el, un, firma, sistema, lapicera}

palabras que quiero saber si son válidas: firma, melanie, los, pato

Una forma de saber si cada palabra es válida sería recorrer toda la lista. Si llegamos al final de la misma sin encontrar la palabra, significa que no es válida. Si la encontramos, sabremos que es válida y podemos parar la búsqueda allí. Esta sería una forma correcta de resolver el problema pero demoraría mucho tiempo: para cada elemento que queremos saber si está en la lista, hay que recorrerla entera. Si la lista es larga y tengo muchos elementos para preguntar, este enfoque se hace impracticable. Por lo tanto, es $O(n)$ cada búsqueda si hay n palabras válidas. Si hay m búsquedas para hacer, da una complejidad total de $O(n \cdot m)$.

Otra forma de resolver el problema sería ordenar la lista y hacer búsqueda binaria en ella. Así, cada búsqueda tomaría $O(\log n)$ en vez de $O(n)$, lo que nos daría un costo total de $O(m \log n)$ si sumamos todas las búsquedas. No olvidemos que tuvimos que ordenar la lista (que toma $O(n \log n)$ si tiene n elementos), así que el costo final será de $O(n \log n + m \log n)$.

Esta solución es muy buena, porque por ejemplo si tuviéramos $n = m = 1000000$, la primera solución usaría aproximadamente $1000000000000$ operaciones mientras que la segunda solo $20000000$.

Ahora bien, imaginemos que la lista de palabras no está fija, porque la real academia de este idioma va agregando palabras nuevas. Ahora no solo tendremos que resolver el problema que teníamos antes, sino ir agregando elementos a la lista de palabras cada vez. Como para poder usar búsqueda binaria nuestra lista tiene que estar ordenada, eso significa que con cada palabra nueva tenemos que volver a ordenarla (para pensar: no hace falta llamar al sort de C++ y pagar un costo de $O(n \log n)$ cada vez, porque podemos resolverlo en $O(n)$. Se imaginan cómo?).