En ocasiones anteriores hemos visto que como programadores, podemos escribir el código ingenuo (evidente, fácil, sin pensar, …) o podemos entrenarnos (como los deportistas) para obtener un mejor rendimiento a la hora de escribir nuestro código. Mejor rendimiento es, por supuesto, obtener el resultado más próximo al ideal dentro de las restricciones fijadas por el contexto; por ejemplo, si tenemos un minuto para escribir el algoritmo, alguna optimización podremos hacer, pero no podremos darle demasiadas vueltas (o si prima la legibilidad, etc…).
Una de las cosas que suelo observar, es que muchos programadores se centran en el lenguaje, en el hecho de que están programando una máquina. Sí, eso es evidente, pero si queremos resolver un problema, deberemos comprender en dónde reside su dificultad intrínseca (la que no depende nada más que de ese problema). Y en un algoritmo, su dificultad reside en su complejidad computacional intrínseca (la que no depende de la implementación).
Así pues, ¿dónde está la complejidad de los algoritmos?.
Breve introducción a la complejidad computacional
Cuando en algún sitio lees algo como “tal algoritmo tiene un coste de O(n log n)“, o algo como “la complejidad de ese proceso es O(n2)“, o más rebuscado como que “puede mejorarse a O(|xs| * n + n + n log n)“; lo que te están indicando es algo realmente útil y que no es más, que el número máximo de operaciones necesarias para resolver el problema.
Pongamos algún ejemplo. El siguiente algoritmo para calcular el valor máximo y el valor mínimo de una lista de números tiene por coste O(2n) donde n es la longitud de la lista, veámoslo:
Obviamente puede hacerse en O(n) de esta forma:
(Nota: el algoritmo es sencillo pero, ¿habrías puesto el else?)
Sin embargo, si sabemos que la lista está ordenada, resulta que el coste es O(2). Veamos:
“Si, bueno” te dirás, “¿Pero a que nos referimos con número de operaciones?”. Cierto, en el último algoritmo (con coste O(2)) no se realizan solo dos operaciones, si mirarámos el código que al final tiene que ejecutar la máquina veríamos que realiza muchas operaciones, no solo dos.
En realidad, para no añadir de golpe muchas ideas, arriba he dicho que O(n) (y otros) representa el número de operaciones, pero no es cierto. La complejidad computacional analiza el coste de un algoritmo en todos los sentidos posibles, incluida la cantidad de memoria necesaria para resolverlo, accesos a disco y, en general, cualquier coste que sea digno de tener en cuenta.
Por tanto, si comparamos el primer y segundo algoritmos que hemos escrito, lo que realmente va a marcar una diferencia significativa es la longitud de la lista de entrada y por eso se indica el coste del algoritmo en base a dicha longitud. Por ejemplo, si el número de valores a agregar fueran significativos (máximo, mínimo, promedio, cuadrado, etc…) entonces probablemente, indicaríamos el coste del algoritmo no sólo con la longitud n de la lista, sino también con el número (por ejemplo m) de valores a agregar.
Así, una buena especificación del coste de un algoritmo, tiene que tener en cuenta todas aquellas variables (n, m, …) que de variar, afectarán drásticamente al rendimiento del algoritmo.
Sólo por poner un ejemplo de especificación de rendimiento de algoritmos en base a otra cosa que no sea la velocidad de ejecución (número de operaciones), mostraré la comparativa en cantidad de memoria utilizada. Supongamos que queremos saber, dada una lista de números, que elemento ocupa la posición central tras aplicar una operación a todos los números y ordenar los resultados.
Una forma de hacerlo es usando un array temporal:
Que tiene un coste de memoria O(n) adicionales pues debemos crear un array temporal; sin embargo, en cuanto a velocidad, supuesto que el cómputo con un coste relevante sea funcOperator, sólo requiere O(n) operaciones (estamos suponiendo que el coste de la ordenación puede despreciarse). Sin embargo, es posible hacerlo sin memoria adicional (¿sabrías hacerlo?), veamos como:
En este caso no hace falta memoria adicional, así, el coste de memoria (adicional) es O(0) ¡gratis!; sin embargo, en cuanto a velocidad, en las mismas suposiciones que el de antes, supone un máximo de O(n2) operaciones.
“¿Y saber este tipo de cosas es importante?”, importante no, ¡importantísimo!. Nuestro trabajo consiste en programar y/o utilizar algoritmos para resolver los problemas ¿cómo vamos a elegir los adecuados si no conocemos sus propiedades?. Supón que eres un transportista y que tienes una furgoneta, ¿aceptarías el compromiso de llevar un paquete de Madrid a Barcelona sin conocer previamente el peso y dimensiones del paquete y el peso y dimensiones máximas que soporta tu furgoneta?, si fueras un buen transportista, no lo aceptarías sin conocer esa información y contrastarla.
Muchos programadores “funcionan” escribiendo el código en algún lenguaje y “viendo” por donde “cojea”. Usar un depurador, un profiler, una herramienta de cobertura de código, etc… es muy mala práctica si se usan como el medio a través del cual escribimos nuestro código (son buenas prácticas para prevenir, detectar y corregir los inevitables errores que todos los humanos cometemos). Digamos que todos pondríamos un extintor en la cocina por si se prende fuego ¡pero nadie prende fuego a la cocina para asar un pollo porque tenga un extintor!.
¿Dónde está la complejidad?
Ahora que hemos definido complejidad y hemos visto que es algo a lo que siempre debemos estar atentos para escribir un buen código, ¿cómo la encontramos?, ¿en qué nos tenemos que fijar para saber qué hace que un algoritmo sea más o menos complejo que otros, y encontrar por tanto, las mejores alternativas a nuestros problemas?.
Inevitablemente las herramientas con que contemos para resolver el problema (eg. el lenguaje de programación que debamos usar) serán determinantes (y por tanto debemos conocer las propiedades del lenguaje), sin embargo, habitualmente hablamos de lenguajes de propósito general precisamente, porque en teoría, el lenguaje no impone ninguna limitación a la hora de implementar una estrategia (un algoritmo) determinado (en la práctica si, obviamente).
En los ejemplos anteriores, se han presentado diferentes estrategias (algoritmos) escritos en javascript (implementación), pero cualquier programador puede entender la siguiente estrategia (¡algoritmo!): “ordénese una lista de números; en la primera posición encontraremos el mínimo y en la última posición el máximo”. ¿Hace falta implementar esta estrategia (algoritmo) en algún lenguaje concreto para saber que tiene un coste O(n log n)?, no, claro que no, porque de alguna forma, hemos sintetizado (abstraído) los elementos del problema.
Así, al enfrentarnos a un problema, debemos hacerlo en una primera etapa, pensando únicamente en las propiedades esenciales (abstractas) de los elementos que componen el problema. Luego, en la medida que conocemos esas propiedades, podemos pasar a nuestro “contexto de implementación” y ver cuales de esas propiedades son las más adecuadas para explotar en dicho contexto.
Pero es que además, si tenemos libertad en fijar el contexto de implementación, seremos capaces de elegir el mejor lenguaje en cada situación (o herramientas en general). Por ejemplo, en Solveet propusieron el siguiente problema: “si escribimos consecutivamente todos los números naturales (sin dejar espacios), tendremos algo como 12345678910111213… ¿qué dígito encontraremos en la posición n?”. Sólo tras pensar en el problema, en las propiedades que posee, podemos llegar a soluciones como esta en shell:
(Que no es nada eficiente, pero sí muy concisa). Otros ejemplos son aquellos en los que es posible usar programación lineal, ¡ni siquiera hace falta escribir código para resolver el problema!.
Conclusión
La complejidad de los algoritmos que como programadores nos vemos obligados a escribir y utilizar todos los días, reside únicamente en el problema real que debemos solucionar. Muchas veces creemos que debemos usar tal o cual herramienta, tal o cual lenguaje, tal o cual algoritmo, etc… y no es cierto (si usar un lenguaje es un requisito, entonces forma parte del problema real).
Así, céntrate primero en las propiedades del “enunciado” y juega con ellas mentalmente, la mejor estrategia (algoritmo) te vendrá a la cabeza mientras miras ensimismado por la ventana.
Más información | Teoría de la complejidad computacional.