dsa.js data structures algorithms javascript
2.7.6
Estas son las implementaciones de codificación del libro DSA.js y el repositorio del paquete NPM.
En este repositorio podrás encontrar la implementación de algoritmos y estructuras de datos en JavaScript. Este material se puede utilizar como manual de referencia para desarrolladores o puede actualizar temas específicos antes de una entrevista. Además, podrás encontrar ideas para resolver problemas de forma más eficiente.
Puedes clonar el repositorio o instalar el código desde NPM:
npm install dsa.jsy luego puedes importarlo a tus programas o CLI
const { LinkedList , Queue , Stack } = require ( 'dsa.js' ) ;Para obtener una lista de todas las estructuras de datos y algoritmos disponibles, consulte index.js.
Los algoritmos son una caja de herramientas esencial para todo programador.
Deberá tener en cuenta el tiempo de ejecución de los algoritmos cuando tenga que ordenar datos, buscar un valor en un gran conjunto de datos, transformar datos, escalar su código para muchos usuarios, por nombrar algunos. Los algoritmos son solo el paso que se sigue para resolver un problema, mientras que las estructuras de datos son donde se almacenan los datos para su posterior manipulación. Ambos combinados crean programas.
Algoritmos + Estructuras de Datos = Programas.
De hecho, la mayoría de los lenguajes y bibliotecas de programación proporcionan implementaciones para algoritmos y estructuras de datos básicos. Sin embargo, para utilizar las estructuras de datos correctamente, es necesario conocer las ventajas y desventajas de elegir la mejor herramienta para el trabajo.
Este material te enseñará a:
Todo el código y las explicaciones están disponibles en este repositorio. Puede explorar los enlaces y ejemplos de código de la (carpeta src). Sin embargo, los ejemplos de código en línea no están ampliados (debido a las limitaciones de asciidoc de Github), pero puede seguir la ruta y ver la implementación.
Nota: Si prefiere consumir la información de forma más lineal, entonces el formato de libro sería más apropiado para usted.
Los temas se dividen en cuatro categorías principales, como puede ver a continuación:
Nuggets de informática sin toda la palabrería. (Haga clic para ampliar)
Nuggets de informática sin toda la palabrería
Aprenda a calcular el tiempo de ejecución a partir de ejemplos de código
Aprenda a comparar algoritmos utilizando la notación O grande. (Haga clic para ampliar)
Aprenda a comparar algoritmos utilizando la notación O grande.
Comparación de algoritmos usando la notación Big O
Digamos que desea encontrar los duplicados en una matriz. Usando la notación Big O, podemos comparar diferentes soluciones que resuelven el mismo problema, pero tienen una gran diferencia en el tiempo que lleva hacerlo.
- Solución óptima usando un mapa.
- Encontrar duplicados en una matriz (enfoque ingenuo)
8 ejemplos para explicar con código cómo calcular la complejidad del tiempo. (Haga clic para ampliar)
8 ejemplos para explicar con código cómo calcular la complejidad del tiempo
Complejidades horarias más comunes
Gráfico de complejidad del tiempo
Comprenda los entresijos de las estructuras de datos más comunes. (Haga clic para ampliar)
Comprender los entresijos de las estructuras de datos más comunes
Matrices: integradas en la mayoría de los idiomas, por lo que no se implementan aquí. Complejidad del tiempo de matriz
Lista enlazada: cada nodo de datos tiene un enlace al siguiente (y al anterior). Código | Complejidad del tiempo de la lista vinculada
Cola: los datos fluyen según el método "primero en entrar, primero en salir" (FIFO). Código | Complejidad del tiempo de cola
Pila: los datos fluyen de manera "último en entrar, primero en salir" (LIFO). Código | Complejidad del tiempo de pila
Cuándo utilizar una matriz o una lista enlazada. Conozca las compensaciones. (Haga clic para ampliar)
Cuándo utilizar una matriz o una lista enlazada. Conozca las compensaciones
Utilice matrices cuando...
- Necesita acceder a los datos en orden aleatorio rápidamente (usando un índice).
- Sus datos son multidimensionales (por ejemplo, matriz, tensor).
Utilice listas enlazadas cuando:
- Accederás a tus datos de forma secuencial.
- Desea ahorrar memoria y asignarla solo cuando la necesite.
- Quiere tiempo constante para eliminar/agregar desde los extremos de la lista.
- cuando se desconoce el tamaño requerido: ventaja de tamaño dinámico
Cree una lista, una pila y una cola. (Haga clic para ampliar)
Cree una lista, una pila y una cola desde cero
Cree cualquiera de estas estructuras de datos desde cero:
- Lista enlazada
- Pila
- Cola
Comprenda una de las estructuras de datos más versátiles de todas: Hash Maps. (Haga clic para ampliar)
HashMaps
Aprende a implementar diferentes tipos de Maps como:
- HashMap
- ÁrbolMapa
Además, conozca la diferencia entre las diferentes implementaciones de Maps:
HashMapahorra más tiempo. UnTreeMapocupa más espacio.- La complejidad de la búsqueda
TreeMapes O(log n) , mientras que unHashMapoptimizado es O(1) en promedio.- Las claves de
HashMapestán en orden de inserción (o aleatorias según la implementación). Las claves deTreeMapsiempre están ordenadas.TreeMapofrece algunos datos estadísticos de forma gratuita, como: obtener mínimo, obtener máximo, mediana, encontrar rangos de claves.HashMapno lo hace.TreeMaptiene una garantía de siempre O(log n) , mientras queHashMaps tiene un tiempo amortizado de O(1) pero en el raro caso de un refrito, se necesitaría un O(n) .Conocer las propiedades de Gráficos y Árboles. (Haga clic para ampliar)
Conoce las propiedades de Gráficos y Árboles
Graficos
Conozca todas las propiedades de los gráficos con muchas imágenes e ilustraciones.
Gráficos : nodos de datos que pueden tener una conexión o arista con cero o más nodos adyacentes. A diferencia de los árboles, los nodos pueden tener varios padres, bucles. Código | Complejidad del tiempo del gráfico
Árboles
Conozca los diferentes tipos de árboles y sus propiedades.
Árboles : los nodos de datos tienen cero o más nodos adyacentes, también conocidos como hijos. Cada nodo solo puede tener un nodo principal; de lo contrario, es un gráfico, no un árbol. Código | Documentos
Árboles binarios : igual que un árbol pero sólo puede tener dos hijos como máximo. Código | Documentos
Árboles de búsqueda binaria (BST): igual que un árbol binario, pero el valor de los nodos mantiene este orden
left < parent < right. Código | BST Complejidad del tiempoÁrboles AVL : BST autoequilibrado para maximizar el tiempo de búsqueda. Código | Documentos del árbol AVL | Documentos de autoequilibrio y rotaciones de árboles
Árboles rojo-negros : BST autoequilibrado más suelto que AVL para maximizar la velocidad de inserción. Código
Implemente un árbol de búsqueda binario para búsquedas rápidas.
Implemente un árbol de búsqueda binario para búsquedas rápidas
Aprenda cómo agregar/eliminar/actualizar valores en un árbol:
¿Cómo equilibrar un árbol?
De BST desequilibrada a BST equilibrada
1 2 / 2 => 1 3 3
Nunca te quedes atascado resolviendo un problema con 7 sencillos pasos. (Haga clic para ampliar)
Nunca te quedes atascado resolviendo un problema con 8 sencillos pasos
- entender el problema
- Cree un ejemplo simple (aún no hay casos extremos)
- Lluvia de ideas sobre soluciones (algoritmo codicioso, divide y vencerás, retroceso, fuerza bruta)
- Pruebe su respuesta con el ejemplo simple (mentalmente)
- Optimizar la solución
- Escribe código. Sí, ahora puedes codificar.
- Pruebe su código escrito
- Analice la complejidad, tanto en espacio como en tiempo, y asegúrese de optimizarla aún más.
Detalles completos aquí
Domine los algoritmos de clasificación más populares (clasificación por combinación, clasificación rápida, etc.) (Haga clic para ampliar)
Domina los algoritmos de clasificación más populares
Vamos a explorar tres algoritmos de clasificación esenciales O(n^2), que tienen una sobrecarga baja:
Clasificación de burbujas. Código | Documentos
Orden de inserción. Código | Documentos
Orden de selección. Código | Documentos
y luego analice los algoritmos de clasificación eficientes O (n log n) como:
Combinar orden. Código | Documentos
Clasificación rápida. Código | Documentos
Aprenda diferentes enfoques para resolver problemas como divide y vencerás, programación dinámica, algoritmos codiciosos y retroceso. (Haga clic para ampliar)
Aprenda diferentes enfoques para resolver problemas algorítmicos.
Vamos a discutir las siguientes técnicas para resolver problemas de algoritmos:
- Algoritmos codiciosos: toma decisiones codiciosas utilizando heurísticas para encontrar la mejor solución sin mirar atrás.
- Programación dinámica: una técnica para acelerar algoritmos recursivos cuando hay muchos subproblemas superpuestos . Utiliza la memorización para evitar duplicar el trabajo.
- Divide y vencerás: divide los problemas en partes más pequeñas, conquista cada subproblema y luego une los resultados.
- Retroceso: busca todos (o algunos) caminos posibles. Sin embargo, se detiene y regresa tan pronto como nota que la solución actual no funciona.
- Fuerza Bruta : genera todas las soluciones posibles y las prueba todas. (Úselo como último recurso o como punto de partida).
Como programadores, tenemos que resolver problemas todos los días. Si desea resolver bien los problemas, es bueno conocer una amplia gama de soluciones. A menudo, es más eficaz conocer los recursos existentes que encontrar la respuesta usted mismo. Cuantas más herramientas y práctica tengas, mejor. Este libro le ayuda a comprender las compensaciones entre las estructuras de datos y las razones sobre el rendimiento de los algoritmos.
No hay muchos libros sobre algoritmos en JavaScript. Este material llena el vacío. Además, es una buena práctica :)
Sí, abra una incidencia o haga preguntas en el [canal de Slack] (https://dsajs-slackin.herokuapp.com).
Este proyecto también está disponible en un libro. Obtendrá un PDF muy bien formateado con más de 180 páginas + versión ePub y Mobi.
¡Comuníquese conmigo en uno de los siguientes lugares!
@iAmAdrianMejiadsajs.slack.com 
