Escuela Frontend
JavaScript

Introducción al Rendimiento de Algoritmos y Algoritmos de Búsqueda

Leira Sánchez
Autora
Leira Sánchez

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 el 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.

Pre-requisitos

  • 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.

function suma1(n) {
return n + 1;
}

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ía n.

# de operacionesBig O
n + 1O(1)
543O(1)
3n + 1O(n)
21 n^2O(n^2)
  • 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.

CalificacionesBig OTiempo/Complejidad
ExcelenteO(1)Constante
BuenoO(log n)Logarítmico
OkO(n)Lineal
MaloO(n log n)Logarítmico
TerribleO(n^2)Cuadrático
TerribleO(2^n)Exponencial

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
function getLength(array) {
return array.length;
}
getLength([1,2,3,4,5,6,7,88,4,5,77,8,88,3,5,66]); // 16

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
function visitandoLosElementos(arreglo) {
for (let i = 0; i < arreglo.length; i++) {
console.log(`Visitando a ${arreglo[i]}`)
}
return '¡Terminamos!';
}

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
// esta función cuenta las veces que la segunda string aparece en la primera
function busquedaCuadratica(s1, s2) {
// el caso base verifica si los dos strings pasados a la función son iguales
if (s1 === s2) return s1.length;
// si son diferentes, verificamos cuantas veces la segunda aparece en la primera
let count = 0;
// por cada letra en la primera, tenemos que verificar las letras en la segunda
// esto lo logramos con un `for loop` anidado dentro de otro
for (let i = 0; i < s1.length; i++) {
for (let j = 0; j < s2.length; j++) {
if (s1[i+j] !== s2[j]) break;
if (j === s2.length - 1) count++;
}
}
return count;
}
busquedaCuadratica('escuelareactfrontendreactreact react', 'react'); // 4

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.

function fib(num) {
if (num < 2) return num;
return fib(num - 1) + fib(num - 2);
}
fib(10); // 55

Repl.it 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.

AcciónBig O
InsertarO(1)
RemoverO(1)
Acceder (con clave)O(1)
BuscarO(n)
// Ejemplo
const writer = {
name: "Leira",
isAuthor: true,
articles: [
"La Guía Definitiva de Console API",
"CSS-en-JS: Styled Components en React"
]
}
// insertar
writer.twitter = "MechEngSanchez";
// acceder
const nombre = writer.name; // nombre = "Leira"
writer.hasOwnProperty("name"); // true
// buscar
let hasTwitter;
for (const [key, value] of Object.entries(writer)) {
if (key === "twitter" && value !== null) hasTwitter = value;
}
// remover
delete writer["isAuthor"];
MétodoBig O
Object.keys()O(n)
Object.entries()O(n)
Object.values()O(n)
hasOwnProperty()O(1)
deleteO(1)

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.

MétodoBig O
pushO(1)
popO(1)
shiftO(n)
unshiftO(n)
concatO(n)
sliceO(n)
spliceO(n)
ciclos*O(n)

* 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.

function factorial(num) {
// este es nuestro caso base. Si el numero de entrada cumple con algunos de estos casos, devolvemos la respuesta sin tener que calcular el factorial
if (num === 0) return 1;
if (num <= 2) return num;
let result = 1;
// empieza con 2 ya que `result` está inicializado con 1, luego visita cada número, de uno en uno, hasta llegar al número de entrada
for (let i = 2; i <= num; i++) {
// multiplica el número actual por el producto de todos los que vinieron antes
result *= i;
}
return result;
}

En este caso, el salimos del ciclo cuando i sea igual al número de entrada.

Ahora utilizaremos recursión.

function recursiveFactorial(num) {
// este es nuestro caso base. Cuando la recursión se tome con el valor de entrada igual a 2, parará el ciclo
// no es necesario obtener el factorial de 0 y 1 ya que es 1 por lo que no afectaría el valor
if (num <= 2) return num;
// cambiamos el ciclo for por recursión, en este caso empezamos por el número de entrada y bajamos uno a uno hasta llegar a 2
return num * recursiveFactorial(num - 1);
}

El resultado es el mismo, pero el algoritmo que utiliza recursión nos ahorra 6 líneas.

Repl.it Factorial

👉 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.

const palabrasSinOrden = [
'patisserie', 'unspide', 'overclaim',
'theoretician', 'electorally', 'corivalled',
'flamier', 'overteach', 'announcers',
'loggat', 'waragi', 'tibia',
'maggies', 'blashes', 'sealers',
'repurchases', 'soberises', 'corrivalship',
'chicha', 'undrawing', 'insatiable',
'gauzier', 'pentamerous', 'tetchinesses',
'eery', 'scincoids', 'heedless',
'microspecies', 'calottes', 'syes',
'phytologies', 'adjunction', 'myelopathic',
'trackings', 'crap', 'barilla',
'deciduate', 'graduating', 'readvertizement',
'forbears', 'modestly', 'legendarily',
'folk', 'mamba', 'noroviruses',
'escheator', 'vitriolisation', 'abstracter',
'antliate', 'torqued'
];

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

  1. la función acepta un arreglo y un valor
  2. utiliza un ciclo para recorrer el arreglo elemento por elemento
  3. si encuentras el valor que buscas, devuelve el índice
  4. si terminas el ciclo sin encontrar el valor, devuelve -1

Ejemplo Búsqueda Lineal

function busquedaLineal(palabrasSinOrden, palabraABuscar) {
for (let i = 0; i < palabrasSinOrden.length; i++) {
// console.count("ciclcos"); // activa esta linea para contar cuantas visitas hace
if (palabrasSinOrden[i] === palabraABuscar) return i;
}
return -1;
}
busquedaLineal(palabrasSinOrden, "mamba"); // 43

La complejidad de la búsqueda lineal es O(n). Depende cuantos elementos hay en la lista.

Repl.it Búsqueda Lineal

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

  1. la función acepta un arreglo ordenado y un valor

  2. 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

  3. crea un puntero al principio del arreglo y otro al final

  4. mientras el puntero de la izquierda sea menor que el de la derecha

    1. crea un puntero en el centro
    2. si encuentras el valor, devuelve el índice
    3. si el valor en ese puntero es mayor que el valor que buscas, mueve el puntero de la derecha a ese índice menos 1
    4. 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
  5. 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

const palabrasEnOrdenAlfabetico = [
"abstracter", "adjunction", "announcers",
"antliate", "barilla", "blashes",
"calottes", "chicha", "corivalled",
"corrivalship", "crap", "deciduate",
"eery", "electorally", "escheator",
"flamier", "folk", "forbears",
"gauzier", "graduating", "heedless",
"insatiable", "legendarily", "loggat",
"maggies", "mamba", "microspecies",
"modestly", "myelopathic", "noroviruses",
"overclaim", "overteach", "patisserie",
"pentamerous", "phytologies", "readvertizement",
"repurchases", "scincoids", "sealers",
"soberises", "syes","tetchinesses",
"theoretician", "tibia", "torqued",
"trackings", "undrawing", "unspide",
"vitriolisation", "waragi",
];
function busquedaBinaria(palabrasEnOrdenAlfabetico, target) {
if (palabrasEnOrdenAlfabetico.length === 0) return -1;
if (palabrasEnOrdenAlfabetico.length === 1) return palabrasEnOrdenAlfabetico[0] === target ? 0 : -1;
let left = 0;
let right = palabrasEnOrdenAlfabetico.length - 1;
let midpoint;
while (left <= right) {
// console.count("ciclcos"); // activa esta linea para contar cuantas visitas hace
midpoint = left + Math.floor((right - left) / 2);
if (palabrasEnOrdenAlfabetico[midpoint] === target) return midpoint;
if (palabrasEnOrdenAlfabetico[midpoint] < target) left = midpoint + 1;
if (palabrasEnOrdenAlfabetico[midpoint] > target) right = midpoint -1;
}
return -1;
};
busquedaBinaria(palabrasEnOrdenAlfabetico, "mamba"); // 25

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.

CalificacionesBig OTiempo/Complejidad
ExcelenteO(1)Constante
BuenoO(log n)Logarítmico
OkO(n)Lineal
MaloO(n log n)Logarítmico
TerribleO(n^2)Cuadrático
TerribleO(2^n)Exponencial

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.

Recursos

La Guía Definitiva de Métodos de Arreglos

Stack Overflow

Pila de Llamadas

Artículos Relacionados

¿Quieres mejorar tus habilidades de frontend?