Resolver en un orden fijo

Un algoritmo es "un orden fijo para resolver un problema." Recorre los pasos y sale una respuesta; si el orden está mal, el resultado está mal. Con el mismo orden, cualquiera obtiene la misma respuesta. Así que escríbele a una computadora un orden, y siempre hará lo mismo.

Un problema grande no se resuelve de un bocado. Por eso lo partes en problemas pequeños de la misma forma, fijas en qué orden resolverlos, y vuelves a combinar las respuestas de las piezas. Manejar un problema grande así, partiendo, ordenando y combinando, es justo donde empieza el pensamiento computacional. Por difícil que parezca un problema, pártelo pequeño y te cabe en la mano.

Ordenar es poner lo revuelto en fila, en orden. Repite comparar vecinos y enviar el mayor atrás, y la fila queda en orden poco a poco. Uno se asienta por vuelta, así que por revuelto que esté, la fila termina en orden. Ordénalo y encontrar se hace más fácil.

Ordenar comparando vecinos uno por uno explota en comparaciones y se vuelve lento cuando la fila crece. El camino más listo es partir la fila por la mitad, ordenar cada parte, y luego fusionar las dos mitades ordenadas como un cierre. Partir hasta el final deja solo sueltos, y un suelto ya está ordenado. Fusionar es rápido porque solo comparas los dos frentes. Como partes a la mitad, las capas crecen despacio, y cada capa cuesta más o menos el largo de la fila, así que el todo termina mucho más rápido que uno por uno. Esta idea de partir y fusionar es el secreto de ordenar rápido.

Buscar es sacar lo que quieres. Uno por uno es lento, pero en orden cortas a la mitad cada vez y lo encuentras mucho más rápido. Cortar a la mitad funciona solo si está ordenado. Por eso ordenar y buscar son compañeros. Ordénalo una vez y se mantiene rápido para siempre.

La velocidad no se mide en segundos sino por la forma de su crecimiento. Miras cuánto crece el trabajo a medida que las casillas de entrada n se hacen mayores. log n casi no crece, n crece con las casillas, n al cuadrado explota. Y por enredada que esté la fórmula, te quedas solo con el término que más crece. 3n al cuadrado + 5n + 9 es simplemente n al cuadrado. Esta manera de ver solo el término mayor es la O grande. Por eso, con datos grandes, cortar a la mitad le gana a uno por uno sin comparación.

Un algoritmo no solo gasta tiempo; también gasta espacio (memoria). La complejidad espacial mide cuánto crece, con el tamaño de la entrada, el espacio extra que un algoritmo usa más allá de la respuesta. La mismísima lente de big-O que usamos para el tiempo, ahora la ponemos sobre el espacio. Si el espacio extra es siempre una casilla, eso es O(1); si crece con la entrada, eso es O(n). Y el tiempo y el espacio a menudo se canjean entre sí. Arma una tabla por adelantado y gasta más espacio, y se vuelve más rápido; resuélvelo en el lugar y ahorra espacio, y se vuelve más lento. Por eso, al elegir un buen algoritmo, miramos no solo la velocidad sino también el costo del espacio.

Vences un problema grande partiéndolo a la mitad, resolviendo cada parte y volviéndolas a unir. La clave es que las dos piezas no se traslapan. El trabajo hecho en un lado nunca hay que rehacerlo en el otro. Cuando una pieza queda tan chica que ya no puedes partirla, la resuelves de inmediato, y luego unes las piezas resueltas hacia arriba en la respuesta entera. La búsqueda binaria y el ordenamiento por mezcla siguen este molde. Que las piezas no se traslapen es lo que le da fuerza a este enfoque.

La recursión es resolver un problema llamándose a sí misma otra vez con una entrada más chica. En la lección 8 venciste un problema grande partiéndolo a la mitad. Esa partición es justo llamarse a sí mismo otra vez. Así que divide y vencerás y recursión son lo mismo. Lo que de verdad necesita es un suelo para parar. Sin suelo, baja para siempre. Las llamadas se apilan una por una, y al tocar el suelo, se deshacen de vuelta hacia arriba, combinándose en una sola respuesta. Llamarse a sí mismo, un suelo para parar, apilarse y deshacerse. Estos tres son la recursión.

La recursion a menudo vuelve a resolver el mismo problema chico una y otra vez. Solo mira el arbol de Fibonacci, fib(2) aparece por todas partes. Anota una respuesta resuelta y reusala, y nunca resuelves lo mismo dos veces. Eso es memoizacion. Llenar una tabla hacia arriba desde los valores mas chicos abajo es la misma idea al reves. Entonces lo que era exponencialmente lento se vuelve lineal, mucho mas rapido. El divide y venceras tenia piezas que no se traslapan, asi que no habia nada que anotar, pero cuando se traslapan, el solo gesto de anotarlo lo cambia todo.

Un algoritmo voraz elige "lo que se ve mejor ahora mismo" en cada paso. Como escoge paso a paso sin mirar el conjunto, es rápido y simple. Para algunos problemas es de verdad correcto, como dar el cambio empezando por la moneda más grande, o tomar las reuniones que terminan más temprano. Pero cuando el juego de monedas es raro o el camino está enredado, lo mejor que tienes delante no es lo mejor en total y se vuelve una trampa. Así que lo voraz es rápido y acierta seguido, pero no siempre.

Algunas soluciones tiran dados y eligen qué hacer al azar. En quicksort, usar siempre el último valor como referencia se vuelve lento con entradas malas, pero elegir la referencia al azar esquiva esa trampa y es más rápido en promedio. También puedes esparcir puntos dentro de un cuadrado y mirar la fracción que cae en un círculo para estimar un área. Cuantos más lances, más afinada la estimación. Una solución aleatoria no puede prometer la misma respuesta cada vez, pero a cambio es rápida y simple. Cedes un poco de certeza y ganas velocidad.

Un grafo es "un dibujo hecho con puntos (cosas) y líneas (relaciones)." Un punto puede ser cualquier cosa, una línea es una relación entre dos de ellos. El metro, las redes de amigos, la web son todos grafos. Un árbol es el caso especial entre ellos sin ningún ciclo. Así que un árbol también es un tipo de grafo. Mira el mundo como puntos y líneas, y lo que parecía enredado se ve de un vistazo.

Hay dos andares para empezar en un punto y recorrer el grafo entero. El primero en anchura se esparce capa por capa como una onda, lo cercano primero. El primero en profundidad sigue un camino hasta el final y retrocede cuando se atasca. Ambos alcanzan cada punto sin saltarse ninguno, solo en distinto orden. Y cuando las líneas no tienen diferencia de distancia, el orden en que el de anchura los toca es la distancia más corta.

Cuando las aristas tienen distancias distintas, la ruta con menos cruces no es la más rápida. Por eso contar solo por cercanía no basta. Desde el inicio, fijas distancias punto a punto, el más cercano primero, y empujas la frontera de la zona fijada hacia afuera, un punto cada vez. En cada momento eliges el punto no fijado más cercano, lo mejor que tienes delante. Cuando la frontera se extiende por todas partes, sabes la distancia más rápida a cada punto.

Para algunos problemas, basta un pequeño aumento de la entrada para que los casos a revisar exploten, así que aún no se conoce una forma rápida de resolverlos. Piensa en un vendedor que busca la ruta más corta que visita cada ciudad una vez. Pero en muchos de estos, hallar la respuesta es difícil y comprobarla es fácil. Entonces, si comprobar es rápido, ¿resolver también lo es? Esa pregunta se llama P contra NP, y nadie conoce la respuesta todavía. Es un gran misterio sin resolver.

Incluso en un problema difícil donde la respuesta perfecta no se halla rápido, una "suficientemente buena" suele encontrarse pronto. Algunos métodos van un paso más allá y hasta garantizan que la respuesta está "a un pequeño porcentaje de la mejor." Es un trato: cedes algo de exactitud, ganas tiempo. Dedicas más tiempo y es más exacta, menos tiempo y menos exacta. Dónde parar lo elegimos nosotros. Así se cierra toda el área. No podemos resolver cada problema a la perfección, pero con métodos rápidos, estrategias inteligentes y conociendo los límites, un trato sabio te pone una respuesta útil en las manos aun frente a un problema difícil.