javascript-algorithms

Algoritmos y Estructuras de Datos en JavaScript

CI codecov

Este repositorio contiene ejemplos basados en JavaScript de muchos algoritmos y estructuras de datos populares.

Cada algoritmo y estructura de datos tiene su propio LÉAME con explicaciones relacionadas y enlaces para lecturas adicionales (incluyendo algunas a vídeos de YouTube).

Léelo en otros idiomas: English, 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Português, Русский, Türk, Italiana

☝ Nótese que este proyecto está pensado con fines de aprendizaje e investigación, y no para ser usado en producción.

Estructuras de Datos

Una estructura de datos es una forma particular de organizar y almacenar datos en un ordenador para que puedan accederse y modificarse de forma eficiente. Más concretamente, una estructura de datos es un conjunto de valores de datos, las relaciones entre ellos y las funciones u operaciones que se pueden aplicar a los datos.

P - Principiante, A - Avanzado

Algoritmos

Un algoritmo es una especificación inequívoca de cómo resolver una clase de problemas. Es un conjunto de reglas que definen con precisión una secuencia de operaciones.

P - Principiante, A - Avanzado

Algoritmos por Tema

Algoritmos por paradigma

Un paradigma algorítmico es un método o enfoque genérico que subyace al diseño de una clase de algoritmos. Es una abstracción superior a la noción de algoritmo, del mismo modo que un algoritmo es una abstracción superior a un programa de ordenador.

Cómo usar este repositorio

Instalar las dependencias

npm install

Correr ESLint

Es posible que desee ejecutarlo para comprobar la calidad del código.

npm run lint

Correr los tests

npm test

Correr tests por nombre

npm test -- 'LinkedList'

Campo de juegos

Puede jugar con estructuras de datos y algoritmos en el archivo ./src/playground/playground.js y escribir pruebas para ello en ./src/playground/__test__/playground.test.js.

A continuación, simplemente ejecute el siguiente comando para comprobar si el código funciona como se espera:

npm test -- 'playground'

Información útil

Refrencias

▶ Estructuras de datos y algoritmos en YouTube

Notación O Grande

Orden de crecimiento de los algoritmos especificados en la notación O grande.

Gráficas de Notación O grande

Fuente: Big O Cheat Sheet.

A continuación se muestra la lista de algunas de las notaciones de Big O más utilizadas y sus comparaciones de rendimiento frente a diferentes tamaños de los datos de entrada.

Notación O grande Cálculos para 10 elementos Cálculos para 100 elementos Cálculos para 1000 elementos
O(1) 1 1 1
O(log N) 3 6 9
O(N) 10 100 1000
O(N log N) 30 600 9000
O(N^2) 100 10000 1000000
O(2^N) 1024 1.26e+29 1.07e+301
O(N!) 3628800 9.3e+157 4.02e+2567

Complejidad de las operaciones de estructuras de datos

Estructura de Datos Accesso Busqueda Inserción Borrado Comentarios
Colección 1 n n n  
Stack n n 1 1  
Cola n n 1 1  
Lista enlazada n n 1 1  
Tabla hash - n n n En caso de función hash perfecta los costos serían O(1)
Búsqueda por Árbol binario n n n n En el caso de un árbol equilibrado, los costos serían O(log(n))
Árbol B log(n) log(n) log(n) log(n)  
Árbol Rojo-Negro log(n) log(n) log(n) log(n)  
Árbol AVL log(n) log(n) log(n) log(n)  
Filtro de Bloom - 1 1 - Falsos positivos son posibles durante la búsqueda

Complejidad de algoritmos de ordenamiento de arreglos

Nombre Mejor Promedio Pero Memorya Estable Comentarios
Ordenamiento de burbuja n n2 n2 1 Si  
Ordenamiento por inserción n n2 n2 1 Si  
Ordenamiento por selección n2 n2 n2 1 No  
Ordenamiento por Heap n log(n) n log(n) n log(n) 1 No  
Ordenamiento por mezcla n log(n) n log(n) n log(n) n Si  
Quicksort n log(n) n log(n) n2 log(n) No Quicksort utiliza O(log(n)) de espacio en el stack
Shellsort n log(n) depende de la secuencia de huecos n (log(n))2 1 No  
Ordenamiento por cuentas n + r n + r n + r n + r Si r - mayor número en el arreglo
Ordenamiento Radix n * k n * k n * k n + k Si k - largo de la llave más larga