Clase 23 de 24 • Curso de Clean Code y Buenas Prácticas con JavaScript
Contenido del curso
La Big O notation o también conocida como la notación Big O es la expresión matemática de cuánto se tarda en ejecutar un algoritmo en función de la longitud de entrada, normalmente hablando del peor de los casos.
En la práctica se utiliza Big O para clasificar los algoritmos en función de cómo responden a los cambios en el tamaño de la entrada, por lo que los algoritmos con la misma tasa de crecimiento se representan con la misma notación. El uso de la letra O es porque la tasa de crecimiento de una función también se llama orden de la función.
Conocer Big O ayuda y facilita tu trabajo como desarrolladora al ser consciente de la eficiencia de un algoritmo que se traduce en poder crear aplicaciones con un buen rendimiento.
Ahora exploremos los tipos más comunes de Big O al utilizar JavaScript +ES6.
Algoritmo de tiempo constante: O(1)
Este algoritmo es de orden uno y en este orden, independientemente de la complejidad, o sea, el número de elementos, el tiempo es constante.
Esto se puede observar en los algoritmos que devuelven un elemento en una posición ya conocida de un array sin importar el tipo o la longitud.
Código:
const getLast = items => items[items.length-1];
Implementación:
getLast(['a', 'b', 'c', 'd']); //> d(1 iteración) getLast(['a', 'b', 'c', 'd', 'e', 'f', 'g']); //> g(1 iteración)
Algoritmo de tiempo lineal: O(N)
En este tipo de algoritmos, el tiempo en el peor de los casos crece a la par que el número de elementos. Es decir, para N elementos se necesitarán N iteraciones.
Código:
const findIndex = (items, match) => { for (let i = 0, total = items.length; i < total; i++) if (items[i] == match) return i; return -1; };
Implementación:
const array= ['a', 'b', 'c', 'd']; findIndex(array, 'a'); // 0 (1 iteración) findIndex(array, 'd'); // 3 (4 iteraciones) findIndex(array, 'e'); // -1 (4 iteraciones)
Algoritmo de tiempo cuadrático: O(N²)
En este tipo de algoritmo, el tiempo en el peor de los casos es el cuadrado del número de entradas. Esto quiere decir que el tiempo crece exponencialmente en relación con el número de entradas.
Código:
const buildSquareMatrix = items => { let matrix = []; for (let i = 0, total = items.length; i < total; i++){ matrix[i] = []; for (let j = 0, total = items.length; j < total; j++) matrix[i].push(items[j]); } return matrix; };
Implementación:
buildSquareMatrix(['a', 'b', 'c']); /* 9 iteraciones para 3 elementos, retorna: [ ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'] ] /*
Algoritmo de tiempo logarítmico: O(n log n)
Si se trabaja con algoritmos de búsqueda y ordenación, el enfoque suele buscar ser más eficiente cuando se trata de grandes colecciones. En lugar de buscar los elementos uno por uno, se divide los datos y se descartan muchos datos en cada iteración, por lo general la mitad o log base 2.
Si consideramos que estamos un orden log base 2, se podría idealmente encontrar un elemento específico en una colección de un millón de elementos con menos de 20 iteraciones, si se escala el tamaño de la colección a mil millones, entonces se requerían menos de 30 iteraciones.
Si eres una entusiasta del big data, entonces será fácil que imagines la ventaja que tienen este tipo de algoritmos, ya que cuanto mayor sea la colección, mayor será la eficiencia relativa que proporcionen.
Entre estos algoritmos, el más popular que podemos encontrar es el de Quicksort, el cual puede utilizarse para encontrar un elemento específico y ordenar una lista de forma muy eficiente.
Código:
const quickSort = list => { if (list.length < 2) return list; let pivot = list[0]; let left = []; let right = []; for (let i = 1, total = list.length; i < total; i++){ if (list[i] < pivot) left.push(list[i]); else right.push(list[i]); } return [ ...quickSort(left), pivot, ...quickSort(right) ]; };
Implementación:
quickSort( ['q','a','z','w','s','x','e','d','c','r']); // ["a", "c", "d", "e", "q", "r", "s", "w", "x", "z"]
Reinaldo Mendoza
Juan Camilo Angel Fandiño
Carina Payleman
Irving Juárez
Sandra Rosa Arroyo Paredes
Melisa Barrera
Juan Pablo
Hay un curso de BigO muy bueno
Cuál es este curso? no lo encuentro. gracias
No sé si él se referirá a uno completo, pero este tiene una sección específica de notación BigO si también te sirve Juan: Curso de Complejidad Algorítmica con JavaScript Saludos
Otros algoritmos de búsqueda muy famosos que usan O(n log n) son los binarios. Cualquier algoritmo binario tiene esta notación, lo cual la hace muy eficiente, pero para que esto funcione, la data necesita estar ordenada.
La notación Big O es un concepto fundamental en ciencias de la computación y análisis de algoritmos. Se utiliza para describir el rendimiento o complejidad de un algoritmo, especialmente en términos de su tiempo de ejecución o espacio de memoria requerido, a medida que el tamaño de la entrada aumenta.
Importancia:
La notación Big O en JavaScript se refiere a una forma de analizar y comparar el rendimiento y la eficiencia de los algoritmos y las funciones en términos de su tiempo de ejecución y uso de memoria.
O(1)
<const getLast = items => items[items.length-1]; console.log(getLast(['a', 'b', 'c', 'd'])); //> d(1 iteración) console.log(getLast(['a', 'b', 'c', 'd', 'e', 'f', 'g'])); //> g(1 iteración)>
O(N)
<const findIndex = (items, match) => { for (let i = 0, total = items.length; i < total; i++) if (items[i] == match) return i; return -1; }; const array= ['a', 'b', 'c', 'd']; console.log(findIndex(array, 'a')); // 0 (1 iteración) console.log(findIndex(array, 'd')); // 3 (4 iteraciones) console.log(findIndex(array, 'e')); // -1 (4 iteraciones)>
O(N²)
<const buildSquareMatrix = items => { let matrix = []; for (let i = 0, total = items.length; i < total; i++){ matrix[i] = []; for (let j = 0, total = items.length; j < total; j++) matrix[i].push(items[j]); } return matrix; }; console.log(buildSquareMatrix(['a', 'b', 'c'])); /* 9 iteraciones para 3 elementos, retorna: [ ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'] ] */ >
O(n log n)
<const quickSort = list => { if (list.length < 2) return list; let pivot = list[0]; let left = []; let right = []; for (let i = 1, total = list.length; i < total; i++){ if (list[i] < pivot) left.push(list[i]); else right.push(list[i]); } return [ ...quickSort(left), pivot, ...quickSort(right) ]; }; console.log(quickSort( ['q','a','z','w','s','x','e','d','c','r'])); // ["a", "c", "d", "e", "q", "r", "s", "w", "x", "z"]>
