Algoritmos y complejidad

Un algoritmo es, en el fondo, una receta: una secuencia finita de pasos precisos que transforma una entrada en una salida deseada. La receta de cocina, las instrucciones para armar un mueble y el procedimiento para cambiar una rueda son algoritmos en sentido amplio. Lo que los hace algoritmos no es la máquina ni el lenguaje, sino dos exigencias: que terminen (que no se queden dando vueltas para siempre) y que sean correctos (que entreguen la respuesta que prometen, para toda entrada válida).

Cuando alguien dice 'este programa funciona', lo que de verdad debería poder sostener es 'este algoritmo termina y es correcto'. Lo demás es confianza a ciegas. Y como un programa puede correr millones de veces con entradas distintas, no basta con probarlo unas cuantas y cruzar los dedos: hay que argumentar por qué acierta siempre.

Pero ni terminar ni ser correcto alcanzan para que un algoritmo sirva en la práctica. También tiene que ser viable: hacer su trabajo en un tiempo y con una memoria que el mundo real pueda pagar. Ahí aparece la idea que ordena toda esta área: el costo de un algoritmo no se mide en segundos (los segundos dependen del hardware de turno), sino en como crece el trabajo a medida que crece la entrada. A eso se le llama complejidad.

Correctitud: por qué creerle a un algoritmo

Demostrar que un algoritmo es correcto no es testearlo con muchos ejemplos: es argumentar, de una vez, que para cualquier entrada válida entrega la salida correcta. Las herramientas son viejas y honestas. Una es el invariante: una afirmación que se mantiene cierta en puntos clave del algoritmo, sin importar los pasos intermedios. Si estas buscando el máximo de una lista, un invariante típico es 'hasta aquí, mi variable guarda el mayor valor visto'. Si logras mostrar que el invariante arranca cierto y se preserva en cada paso, y que al terminar implica la respuesta correcta, tienes una demostración.

La otra herramienta es la inducción matemática, que es la forma formal de la recursión: pruebas el caso base y luego que, si la propiedad vale para n, también vale para n más uno. Juntas, inducción e invariantes permiten sostener que un algoritmo acierta sin tener que correrlo ni una sola vez.

Cuánto cuesta: la notación O grande

Dos algoritmos pueden resolver el mismo problema y, sin embargo, uno ser mil veces más rápido que el otro con entradas grandes. Para compararlos sin programarlos ni medirlos con cronómetro se usa la complejidad algorítmica, y su lenguaje habitual es la notación O grande.

La idea es describir como crece el trabajo cuando la entrada se hace muy grande, ignorando las constantes y los detalles menores. Si un algoritmo recorre una lista de n elementos una sola vez, es O(n): el trabajo crece en proporción al tamaño. Si compara cada elemento con todos los demás, es del orden de n al cuadrado: duplicar la entrada cuadruplica el trabajo. Otras familias comunes son O(1), que significa costo constante sin importar el tamaño; O(log n), que crece tan lentamente que parece casi magia (es lo que consigue la búsqueda binaria); y O(n log n), típico de los buenos algoritmos de ordenamiento.

Lo importante es que la notación O grande describe una tendencia, no un tiempo. Un O(n) y un O(n^2) pueden parecer equivalentes con mil elementos; con un millón, el primero hace un millón de operaciones y el segundo un billón. La curva, no el punto, es lo que define si un algoritmo escala.

Existen también la notación Omega grande, que acota el costo por abajo (dice 'como mínimo tanto'), y la notación Theta, que acota por arriba y por abajo a la vez y por eso pinta el crecimiento real. La O grande es la más popular porque, al ser pesimista, ofrece una garantía.

Peor caso y caso promedio

Un mismo algoritmo no cuesta lo mismo con todas las entradas del mismo tamaño. Buscar un valor en una lista puede terminar al primer elemento, a la mitad o, si el valor no está, recorrerla entera. Por eso se distinguen el peor caso (el escenario que más le cuesta, y por tanto la garantía que ofreces: nunca más lento que esto) y el caso promedio (lo que cabe esperar en uso habitual). En la práctica, los ingenieros miran sobre todo el peor caso, porque la promesa que importa es 'no se va a caer ni a colgar en condiciones desfavorables'.

Hay un matiz útil: el análisis amortizado, que reparte el costo de una operación cara entre las muchas baratas que la rodean. Un arreglo dinámico, por ejemplo, es barato de extender casi siempre, pero de tanto en tanto hay que duplicar su memoria: amortizado, sigue siendo constante en promedio. Mirar solo el pico engaña.

Por qué la diferencia es real: O(n) contra O(n^2)

Podría parecer que la complejidad es un refinamiento teórico. No lo es: decide si algo es usable. Imagina una tarea que hoy, con n igual a diez mil, tarda un segundo con un algoritmo O(n^2). Si mañana necesitas procesar cien mil elementos, diez veces más, el trabajo se multiplica por cien: pasa de un segundo a casi dos minutos. Con un millón, a casi tres horas. El mismo problema, resuelto con un algoritmo O(n log n), tardaría una fracción de segundo en todos los casos.

Este es el motivo por el que un programa que 'anda rápido' en la demo, con datos de juguete, se cae a pedazos en producción, con datos reales. No es que la máquina sea más lenta ni que el código tenga un bug: es que el algoritmo elegido no escalaba, y el crecimiento lo revela cuando ya es tarde.

Tratable e intratable: P, NP y la pregunta del millón

Algunos problemas se pueden resolver en tiempo polinomial (algo como n, n^2 o n^3), y a esa familia se le llama clase P: son los considerados tratables, los que aguantan el crecimiento. Otros problemas, en cambio, crecen de tal manera que ni toda la energía del universo alcanzaría para resolverlos a fondo cuando la entrada se hace grande: son los intratables.

Ahí entra la clase NP, mal entendida a menudo. NP no significa 'no polinomial'. Significa que, aunque no sabemos resolver el problema rápido, si podemos verificar rápido una solución propuesta. Un Sudoku gigante puede ser trabajoso de resolver, pero comprobar que una solución cumple todas las reglas se hace en un momento: está en NP. Todo lo que está en P también está en NP (si lo resuelves rápido, también lo verificas rápido).

La gran pregunta abierta de la disciplina es P versus NP: son lo mismo? Todo problema cuya solución se verifica rápido se puede también resolver rápido? Casi todo el mundo cree que no, pero nadie lo ha demostrado. Lo que si se sabe es que existen los problemas NP-completos, los más duros de NP: si encontraras un algoritmo rápido para uno solo de ellos, tendrías uno para todos. El problema del viajante, encontrar la ruta más corta que pasa por todas las ciudades, es el ejemplo clásico. Cuando te topas con un problema NP-completo en la práctica, dejas de buscar la solución óptima y aceptas una heurística: una respuesta buena, no garantizada perfecta, en un tiempo razonable.

Lo que ni siquiera se puede decidir

Hay un escalón más abajo del costo: hay problemas para los que directamente no existe ningún algoritmo que los resuelva, por más tiempo y memoria que entregues. No son difíciles: son imposibles. El ejemplo fundacional es el problema de la parada: decidir, mirando el código de un programa arbitrario y una entrada arbitraria, si ese programa va a terminar o a quedarse corriendo para siempre. Alan Turing demostró que ningún algoritmo general puede responder eso con seguridad en todos los casos.

Eso es la indecidibilidad, y arrastra consecuencias prácticas. Significa, por ejemplo, que no puede existir un analizador perfecto que revise cualquier programa y te diga si tiene bugs, o si es seguro, o si va a terminar. Siempre habra casos que escapan a cualquier verificador automático. No es una limitación de ingeniería que mejorará con mejores máquinas: es un teorema. La computadora, por más potente que sea, tiene una frontera dura trazada por la matemática.

Lo que conviene recordar

Un algoritmo es una receta que debe terminar y ser correcta, y que además debe ser viable. La correctitud se demuestra con invariantes e inducción, no a base de pruebas. El costo se mide por como crece, no por cuanto tarda hoy, y la notación O grande es su lengua franca. La diferencia entre O(n) y O(n^2) no es teoría: es la diferencia entre un sistema que escala y uno que se cae. Y existen problemas intratables, otros que parecen intratables pero cuya dureza es una conjetura (P versus NP), y otros, finalmente, que ninguna máquina podrá resolver jamás. Saber en que casilla cae un problema es, muchas veces, la mitad del trabajo.