En el mundo del software, no todo es escribir código y programar como si no hubiese un mañana. Más allá de entender nuestro objetivo y lo que queremos hacer al programar, existen otras variables que tenemos que tener en cuenta al momento de desarrollar software. Dígase complejidad, mantenibilidad, escalabilidad, algoritmos a implementar, etcétera. Una de las más importantes es el rendimiento de nuestra aplicación en cuanto a la implementación de un algoritmo.
El rendimiento de nuestro algoritmo permitirá, no sólo hacernos sentir como que somos los dioses de la tecnología al hacer que el software que hemos creado haga mil y un cosas por segundo, sino también ayudará a que el usuario (dígase usuario común o un profesional en el ámbito tecnológico) no tenga que esperar durante horas a que la tarea para la que nuestro software fue desarrollado, se cumpla, sin importar que las computadoras y dispositivos de hoy en día sean lo más capaces para desarrollar una larga lista de tareas medianamente complejas y otra lista un poco menos larga de tareas complejas.
Existen varios factores que interfieren al hablar de rendimiento en nuestro algoritmo, como lo son: el uso de espacio en disco, de memoria para su ejecución, tiempo de ejecución en general, etcétera.
Una de las herramientas más importantes para determinar el rendimiento de nuestro algoritmo es la Notación Big O.
NOTACION BIG O
La notación Big O es una herramienta muy funcional para determinar la complejidad de un algoritmo que estemos utilizando, permitiéndonos medir su rendimiento en cuanto a uso de espacio en disco, recursos (memoria y ciclos del reloj del CPU) y tiempo de ejecución, entre otras, ayudándonos a identificar el peor escenario donde el algoritmo llegue a su más alto punto de exigencia.
Los términos de complejidad Big O más utilizados son:
Cuando investigues un poco más sobre el tema, te encontrarás con temas matemáticos algo complejos, que si tú especialidad no eran las matemáticas, creo que te sentirás algo confundido y ansioso. Pero no te preocupes, te explicaré lo más amigable y entendible posible, más cuando hablemos de logaritmos. A su vez, acompañaré la explicación con un ejemplo en Javascript relacionado con el tema.
O(1): Complejidad Constante
La complejidad constante nos indica que, sin importar el tamaño de entrada o salida, el tiempo de ejecución y recursos utilizados por nuestro algoritmo siempre será el mismo. Podemos verlas como funciones “estáticas” debido a que siempre se comportarán de la misma manera, no importa las veces que sea ejecutada ni donde. Por ejemplo:
Tomando el ejemplo anterior, podemos ser testigos de un pequeño algoritmo con complejidad constante. Esto gracias a que, no importa el tamaño del arreglo que sea pasado como argumento, el resultado siempre será obtener el último elemento que este arreglo contenga. La única variante será el resultado entregado, ya que el dato contenido en el último espacio de un arreglo puede variar.
O(n): Complejidad Linear
Decimos que un algoritmo tiene complejidad linear, cuando su tiempo de ejecución y/o uso de recursos es directamente proporcional (es decir que se incrementa linealmente) al tamaño del valor de entrada necesario para la ejecución del algoritmo. Usando el siguiente fragmento como ejemplo:
Para entenderlo de una manera mucho más sencilla, podemos compararlo con una actividad sumamente común como leer un libro o ver una película. El tiempo que tardemos en terminar de leer dicho libro o ver dicha película, dependerá de su duración. Si la película dura una hora, tardaremos una hora en terminar de ver la película. Si el libro es de 100 páginas y lees 50 páginas en hora (realmente depende en tu capacidad de lectura y comprensión), entonces tardarás 2 horas en terminar de leer dicho libro.
O(log n): Complejidad Logarítmica
La complejidad logarítmica es dada cuando el tiempo de ejecución o uso de recursos es directamente proporcional al resultado logarítmico del tamaño del valor de entrada. Es decir, si tenemos un dato de entrada cuyo tamaño es 10 y nos toma 1 segundo en la implementación del algoritmo, significa que por un valor de entrada cuyo tamaño es 100, nos debe tomar 2 segundos en realizar el algoritmo, un valor de 1000 nos debe tomar 3 segundos y así consecuentemente.
Un ejemplo muy claro es al momento de ejecutar una búsqueda binaria. En este algoritmo particionamos un arreglo, previamente ordenado, en dos. Tomamos el indice medio como punto de referencia para obtener el valor que se encuentra a la mitad del arreglo. Si el dato a la mitad del arreglo es igual al dato que estamos buscando, regresamos el indice medio sumándole el prefijo que usaremos como base para encontrar el espacio donde el dato que estamos buscando se ubica. Consecuentemente, si el número que buscamos es mayor al dato medio del arreglo, buscaremos en el lado derecho del arreglo y le sumaremos a nuestro prefijo el indice medio; por otra parte, si el dato que buscamos es menor al dato que se encuentra a la mitad del arreglo, buscaremos en el lado izquierdo del arreglo. Posteriormente utilizamos el prefijo que tenemos actualmente para que sea la base de la siguiente iteración de manera recursiva. Repetimos este ciclo hasta encontrar el número dado por parámetro en la función.
O(n ^ 2): Complejidad Cuadrática
Encontramos complejidad cuadrática en los algoritmos, cuando su rendimiento es directamente proporcional al cuadrado del tamaño del valor de entrada. Es decir, si tenemos como dato de entrada un arreglo con un tamaño de 4 elementos que queremos comparar para ver si hay elementos repetidos, tendremos que hacer 16 comparaciones en total para completar nuestro algoritmo. Esta complejidad es común encontrarla en algoritmos de ordenamiento de datos como el método de la burbuja, el de inserción y el método de selección, entre algunos otros.
La complejidad puede incrementarse con más ciclos anidados, hasta llegar a ser una complejidad n * n.
O(2 ^ n): Complejidad Exponencial
Cuando un algoritmo tiene complejidad exponencial, su rendimiento se incrementa al doble cada vez que se agregue un nuevo dato al valor de entrada, por ende, incrementando su tamaño de manera exponencial. Esto quiere decir que si tenemos un arreglo con 1 elemento y nos toma 10 segundos ejecutar el algoritmo, con 2 elementos nos deberá tomar 20 segundos, con 3 nos deberá tomar 30 y así de manera sucesiva.
Un ejemplo bastante común de complejidad exponencial es la sucesión de Fibonacci.
