Los algoritmos de clasificación te permiten organizar los elementos de una lista de diferentes maneras. Algunas de las maneras más populares son en orden numérico, orden alfabético, orden ascendente, y orden descendente.
Ordenar una lista gigantesca de elementos puede ser muy costoso en términos de memoria y rapidez. Por esto, debemos optimizar los algoritmos para hacer mejor uso de los recursos disponibles.
Además, conocer estos algoritmos te beneficiará a la hora de entrevistarte como desarrollador. Muchas compañías examinan tus habilidades con las estructuras de datos y algoritmos como parte de su proceso de entrevista.
Estos son temas que generalmente son impartidos como parte del currículo de ciencias de cómputos e ingeniería en computadoras.
Claro, eso no quiere decir que tengas que aprenderte estos algoritmos de memoria, pero si deberías entender la lógica detrás de ellos.
Para entender
- Conocimiento intermedio de JavaScript (ciclos, objetos, arreglos)
Conocimiento intermedio de JavaScript (ciclos, objetos, arreglos)
Cómo correr los ejemplos
Durante este artículo estaré utilizando repl.it para demostrar los ejemplos. Cada ejemplo tendrá un enlace donde podrás correr el código. Además podrás fork para que experimentes con el algoritmo o añadas notas.
Al entrar a los enlaces de repl.it podrás darle play o Run al algoritmo para ver el resultado. Para ver el código, presiona Show files. Puedes copiarlo a tu cuenta presionando Fork repl.
👉 Recomiendo que intentes construir el algoritmo antes de proceder a mi solución. Puedes hacerlo en repl.it, localmente en tu computadora, o cualquier otro método que te permita correr funciones de JavaScript.
Big O
También conocida como notación asintótica, la notación Big O se utiliza para calificar el rendimiento de los algoritmos según crece la cantidad de elementos a procesar. Big O clasifica los algoritmos de acuerdo a la magnitud del peor escenario posible. Nos provee una manera de etiquetar los algoritmos de acuerdo a su rendimiento, algo así a como la Escala Richter califica los sismos. Big O se encarga de describir la tendencia del tiempo que le tomará al algoritmo a procesar todos los elementos de entrada. Por eso muchas veces se habla de Big O como el tiempo o tiempo de complejidad: tiempo constante, tiempo linea, etc..
Para obtener la calificación Big O de algún algoritmo debemos contar cada operación que hace.
Por ejemplo, en la función suma1, solo hay una operación: n + 1. No importa el valor de n, siempre habrá una sola operación.
Notación
Big O se expresa de la siguiente manera: O(# de operaciones), donde # de operaciones es la cantidad de operaciones que has contado. En el ejemplo anterior, Big O sería constante por lo que la notación sería: O(1).
Guías
Te puedes dejar llevar por las siguientes guías para calcular el Big O de algún algoritmo:
- Las constantes no importan. Por ejemplo, si contaste 3n operaciones, el Big O sería
n. Esto es porque a Big O solo le importa la magnitud a medida que la entrada crece. Si fuese 3n + 1, Big O también serían.
- Solo nos preocupamos por los términos mayores. En
2n^3 + 3n^2 + n + 89, solo nos interesa el término con el orden mayor,2n^3. Por lo tanto, el Big O sería O(n^3).
También hay algunas guías específicas para código.
- Las asignaciones de variables siempre son constantes – no hace diferencia asignarle 1 o 1000000 a una variable, toma el mismo tiempo.
- Las operaciones aritméticas son constantes
- Para los ciclos, Big O es el largo del ciclo multiplicado por complejidad de lo que sucede dentro del ciclo: O(m x n).
Complejidades
En la siguiente tabla podrás ver diferentes complejidades y como se califican.
La calificación es una manera subjetiva de describir el rendimiento del algoritmo, no es formal. Es simplemente una manera de describir el rendimiento. De esta manera pueden tener una idea de que complejidad es mejor que otra.
O(1) Complejidad Constante
Cuando un algoritmo tiene complejidad constante, quiere decir que el tiempo de procesamiento es el mismo sin importar el tamaño de entrada o de salida.
Ejemplo de Complejidad Constante
La longitud de un arreglo no es una propiedad calculada, es una propiedad que se actualiza automaticamente mientras crece el arreglo. Por lo tanto, buscar la longitud de un arreglo no depende del tamaño del arreglo y la complejidad de esta acción es constante.
O(n) Complejidad Lineal
Un algoritmo tiene complejidad lineal cuando el tiempo de procesamiento es directamente proporcional al tamaño de la entrada. Un ejemplo de esto es cuando visitamos los elementos de un arreglo. El tiempo será proporcional a la cantidad de elementos en el arreglo.
Ejemplo de Complejidad Lineal
Si pensamos en el arreglo como un vecindario y los elementos como las casas, el tiempo que te toma ir a todas las casas (sin entrar por un café, claro) va a depender de cuantas casas tiene el vecindario.
Es posible que no le demos la vuelta entera a un ciclo, pero como a Big O solo le importa el peor escenario, entonces se toma el caso en el que vas por todos los elementos.
O(log n) Complejidad Logarítmica
La complejidad es logarítmica cuando el tiempo de procesamiento es proporcional al logaritmo del tamaño de entrada. Veremos un ejemplo en la sección de búsqueda binaria.
O(n^2) Complejidad Cuadrática
Cuando tenemos un ciclo anidado dentro de otro, donde cada cual depende del tamaño de la entrada, suele ser de complejidad O(n^2). Así mismo, mientras más niveles de anidación que dependan del tamaño de la entrada, mayor el orden de complejidad.
Ejemplo de Complejidad Cuadrática
✨ Repl.it ✨
O(2^n) Complejidad Exponencial
La complejidad exponencial es cuando un algoritmo cuyo tiempo de procesamiento se dobla con cada adición al tamaño de la entrada. Por ejemplo, si le toma un 10 procesar un elemento, a un algoritmo con complejidad exponencial le tomaría 100 segundos procesar dos elementos.
Ejemplo Complejidad Exponencial – Fibonacci
Uno de los algoritmos más populares con esta complejidad es la sucesión de Fibonacci.
👉 En este enlace podrás ver las gráficas de las complejidades más comunes y la complejidad de las estructuras de datos y algoritmos más utilizados.
Rendimiento de los Objetos
Los objetos son un tipo de lista en el que los elementos tienen una clave y un valor. No mantienen ningún orden particular, pero proveen acceso rápido a elementos específicos. También remueven y añaden elementos tiempo constante.
Rendimiento de los Arreglos y sus Métodos
Otro tipo de listas es el arreglo. A diferencia de los objetos, los arreglos sí mantienen orden.
* Algunos métodos de ciclos para arreglos: forEach, map, filter, reduce.
Recursión o Recursividad
Un concepto que será muy útil ya que es utilizado en muchos algoritmos es la recursión. Recursión es cuando un algoritmo se llama a si mismo. El problema se divide en pedazos más pequeños que son procesados por el mismo algoritmo. La solución del problema depende de la solución de cada uno de estos pedazos. La mayoría de los algoritmos que usan recursión también pueden escribirse iterativamente. La secuencia de Fibonacci, que vimos en la sección de complejidad, es un ejemplo de un algoritmo recursivo.
Antes de correr una función recursiva, es importante asegurarnos de que tiene una manera de salir del ciclo. Al fin y al cabo, la recursión es simplemente otra manera de escribir un ciclo. Cada llamada a la función recursiva es añadida al Call Stack (Pila de llamadas). Una vez la llamada es ejecutada, es eliminada del Call Stack. El famoso stack overflow ocurre cuando la cantidad de llamadas superan el espacio disponible. Muchas veces es producido por la función llamándose a si misma infinitamente.
Ejemplo Factorial
Otro ejemplo es una función que calcula el factorial. Factorial se define como el producto de un entero y todos los enteros menores que él.
Primero, veámoslo escrito iterativamente.
En este caso, el salimos del ciclo cuando i sea igual al número de entrada.
Ahora utilizaremos recursión.
El resultado es el mismo, pero el algoritmo que utiliza recursión nos ahorra 6 líneas.
👉 Busca recursion en Google, jeje.
Algoritmos de Búsqueda
Los algoritmos de búsqueda te permiten encontrar algún elemento en una lista. Si la lista es inmensa, por ejemplo, todas las canciones disponibles en Spotify, encontrar el elemento que buscas puede tomar mucho tiempo. En esta sección, la lista siempre será representada por un arreglo.
Búsqueda Lineal
La búsqueda lineal se trata de cuando buscamos un elemento visitando cada elemento uno a uno hasta encontrar el que queremos. En una lista gigante puede costarnos mucho en términos de tiempo y recursos. Mira la siguiente lista, por ejemplo. Son palabras en inglés sin ningún orden particular.
Si quisieramos encontrar la palabra mamba en esta lista, sin saber en qué lugar se encuentra, tendríamos que hacer 43 visitas. ¡Imagínate buscando una canción particular en Spotify una a una 😱! Claro, si las palabrasSinOrden hubiesen estado organizadas de otra manera, la cantidad de visitas cambiaba. Si mamba hubiese estado en la primera posición, la encontrabamos en la primera visita. Como desconocemos el orden de los elementos, siempre estimamos cual sería el peor caso.
Pseudo-Código para la Búsqueda Lineal
- la función acepta un arreglo y un valor
- utiliza un ciclo para recorrer el arreglo elemento por elemento
- si encuentras el valor que buscas, devuelve el índice
- si terminas el ciclo sin encontrar el valor, devuelve -1
Ejemplo Búsqueda Lineal
La complejidad de la búsqueda lineal es O(n). Depende cuantos elementos hay en la lista.
Búsqueda Binaria
La búsqueda binaria es un algoritmo tipo “divide y conquista”. Siempre se empieza con una lista ordenada de alguna manera (alfabética, numérica, etc.). Empezamos buscando el elemento en el centro de la lista. Si el elemento es mayor que el valor del centro, entonces limitamos la búsqueda a la segunda mitad de la lista. Si es menor, a la primera. Con cada iteración, reducimos el tamaño de la lista por la mitad.
Un ejemplo de esto es cuando estás buscando una página específica en un libro impreso.
Pseudo-Código para la Búsqueda Binaria
- La función acepta un arreglo ordenado y un valor
- La función devuelve el índice donde se encuentra el valor en el arreglo o -1 si el valor no se encuentra en el arreglo
- Crea un puntero al principio del arreglo y otro al final
- Mientras el puntero de la izquierda sea menor que el de la derecha
- Crea un puntero en el centro
- Si encuentras el valor, devuelve el índice
- Si el valor en ese puntero es mayor que el valor que buscas, mueve el puntero de la derecha a ese índice menos 1
- Si el valor en ese puntero es menor que el valor que buscas, mueve el puntero de la izquierda a ese índice más 1
- Si llegas al punto en que el puntero de la izquierda sobrepasa al puntero de la derecha, quiere decir que el valor no existe en el arreglo. Devuelve -1
👉 Antes de pasar a la siguiente parte, trata de hacer esta función. Luego, podrás comparar con mi versión.
Ejemplo de Búsqueda Binaria
En la primera visita llegamos al elemento en el índice 24, maggies. Esta palabra está antes, alfabéticamente, que mamba. Por lo tanto, movemos el puntero de la izquierda hacia midpoint + 1. En total, tenemos que hacer cinco visitas para encontrar la palabra mamba. Es mucho más eficiente que la búsqueda lineal que nos tomaba 43 visitas, o 50 en el peor caso.
La complejidad de la búsqueda binaria es O(log n).
✨ Repl.it ✨
✨ Visualización de Búsqueda Binaria ✨
Conclusión
Big O es una manera de describir el rendimiento de un algoritmo basado en el tamaño de la entrada. Utiliza el peor caso posible para estimarlo. Solo toma en consideración la magnitud de las operaciones.
Recursión es cuando una función se llama a si misma. El problema se rompe en pedazos más pequeños que son procesados por la misma función. Es importante tener una condición que rompa el ciclo para evitar el stack overflow.
La búsqueda lineal tiene un rendimiento de O(n) ya que visita cada elemento hasta encontrar el valor que busca. Si la lista está ordenada de alguna manera, se puede mejorar el rendimiento utilizando búsqueda binaria. Cada iteración reduce el numero de posibilidades por la mitad.
Estos conceptos son importantes para escribir código eficiente. Además, son temas populares para las entrevistas.