贪心算法 旅行
JavaScript 算法与数据结构本仓库包含了多种基于 JavaScript 的算法与数据结构。每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。Read
本仓库包含了多种基于 JavaScript 的算法与数据结构。
每种算法和数据结构都有自己的 README 并提供相关说明以及进一步阅读和 YouTube 视频。
Read this in other languages:English ,繁体中文
数据结构数据结构是在计算机中组织和存储数据的一种特殊方式，它可以高效地访问和修改数据。更确切地说，数据结构是数据值的集合，它们之间的关系、函数或操作可以应用于数据。
链表队列栈哈希表堆优先队列字典树树二分查找AVL 树红黑树 后缀树 线段树 或 间隔树 二叉索引树图(有向图与无向图)并查集算法算法是如何解决一类问题的明确规范。 算法是一组精确定义操作序列的规则。
算法主题数学阶乘斐波那契数素数检测(排除法)欧几里得算法-计算最大公约数(GCD)最小公倍数(LCM)整数拆分集合笛卡尔积-多集合结果幂集-该集合的所有子集排列(有/无重复)组合(有/无重复)洗牌算法-随机置换有限序列最长公共子序列(LCS)最长递增子序列Shortest Common Supersequence(SCS)背包问题-"0/1" and "Unbound" ones 最大子数列问题-BF算法 与 动态编程字符串莱温斯坦距离-两个序列之间的最小编辑距离汉明距离-符号不同的位置数克努斯-莫里斯-普拉特算法-子串搜索字符串快速查找-子串搜索最长公共子串搜索二分查找排序冒泡排序选择排序插入排序堆排序归并排序快速排序希尔排序树深度优先搜索(DFS)广度优先搜索(BFS)图深度优先搜索(DFS)广度优先搜索(BFS)戴克斯特拉算法m-找到所有图顶点的最短路径贝尔曼-福特算法-找到所有图顶点的最短路径判圈算法-对于有向图和无向图(基于DFS和不相交集的版本)普林演算法-寻找加权无向图的最小生成树(MST)克鲁斯克尔演算法-寻找加权无向图的最小生成树(MST)拓扑排序-DFS 方法关节点-Tarjan算法(基于DFS)桥-基于DFS的算法欧拉路径与一笔画问题-Fleury的算法 - 一次访问每个边缘哈密顿图-恰好访问每个顶点一次强连通分量-Kosaraju算法旅行推销员问题-尽可能以最短的路线访问每个城市并返回原始城市未分类汉诺塔八皇后问题骑士巡逻算法范式算法范式是基于类的设计的通用方法或方法的算法。 这是一个比算法概念更高的抽象，就像一个 算法是比计算机程序更高的抽象。
BF算法- 查找所有可能性并选择最佳解决方案
最大子数列旅行推销员问题-尽可能以最短的路线访问每个城市并返回原始城市贪心法- 在当前选择最佳选项，不考虑以后情况
背包问题戴克斯特拉算法-找到所有图顶点的最短路径普里姆算法-寻找加权无向图的最小生成树(MST)克鲁斯卡尔算法-寻找加权无向图的最小生成树(MST)分治法- 将问题分成较小的部分，然后解决这些部分
二分查找汉诺塔欧几里得算法-计算最大公约数(GCD)排列(有/无重复)组合(有/无重复)归并排序Quicksort树深度优先搜索(DFS)图深度优先搜索(DFS)动态编程- 使用以前找到的子解决方案构建解决方案
斐波那契数莱温斯坦距离-两个序列之间的最小编辑距离最长公共子序列(LCS)最长公共子串最长递增子序列最短公共子序列0-1背包问题整数拆分最大子数列贝尔曼-福特算法-找到所有图顶点的最短路径回溯法- 类似于 BF算法 试图产生所有可能的解决方案，但每次生成解决方案测试如果它满足所有条件，那么只有继续生成后续解决方案。 否则回溯并继续寻找不同路径的解决方案。
哈密顿图-恰好访问每个顶点一次八皇后问题骑士巡逻B& B 如何使用本仓库 安装依赖npm install 执行测试npm test 按照名称执行测试npm test -- -t 'LinkedList'Playground你可以在./src/playground/playground.js文件中操作数据结构与算法，并在./src/playground/__test__/playground.test.js中编写测试。
然后，只需运行以下命令来测试你的 Playground 是否按无误:
npm test -- -t 'playground'有用的信息 引用▶ YouTube
大O符号大O符号中指定的算法的增长顺序。
源:Big O Cheat Sheet.
以下是一些最常用的 大O标记法 列表以及它们与不同大小输入数据的性能比较。
| 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 |
| 数组 | 1 | n | n | n |
| 栈 | n | n | 1 | 1 |
| 队列 | n | n | 1 | 1 |
| 链表 | n | n | 1 | 1 |
| 哈希表 | - | n | n | n |
| 二分查找树 | n | n | n | n |
| B树 | log(n) | log(n) | log(n) | log(n) |
| 红黑树 | log(n) | log(n) | log(n) | log(n) |
| AVL树 | log(n) | log(n) | log(n) | log(n) |
| 冒泡排序 | n | n^2 | n^2 | 1 | Yes |
| 插入排序 | n | n^2 | n^2 | 1 | Yes |
| 选择排序 | n^2 | n^2 | n^2 | 1 | No |
| 堆排序 | nlog(n) | nlog(n) | nlog(n) | 1 | No |
| 归并排序 | nlog(n) | nlog(n) | nlog(n) | n | Yes |
| 快速排序 | nlog(n) | nlog(n) | n^2 | log(n) | No |
| 希尔排序 | nlog(n) | 取决于差距序列 | n(log(n))^2 | 1 | No |
本文来自投稿，不代表本站立场，如若转载，请注明出处。