本仓库内容是根据哔哩哔哩 《JavaScript 数据结构与算法》 视频整理的学习笔记。
推荐大家按照目录顺序来学习，由浅入深，循序渐进，轻松搞定数据结构和算法。
重点要掌握数据结构与算法的思想和原理，使用哪种编程语言区别不大。
📖 民间定义（权威来源）
- 《数据结构、算法与应用》
- 定义：数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种关系。这些联系可以通过定义相关的函数来给出。
- 解读：强调数据元素之间的关系，以及如何通过函数（操作）来管理这些关系。
- 《数据结构与算法分析》
- 定义：数据结构是 ADT（抽象数据类型 Abstract Data Type）的物理实现。
- 解读：ADT 是逻辑层面的数据操作规范（如
Stack.push()、Queue.dequeue()），而数据结构是它的具体实现（如用数组或链表实现栈）。
- 中文维基百科
- 定义：数据结构是计算机中存储、组织数据的方式。精心选择的数据结构可以带来最优效率的算法。
- 解读：强调数据结构与算法的关系，好的数据结构能提升算法效率。
- ChatGPT
- 定义：数据结构是计算机科学中用于组织和存储数据的一种方式。它描述了数据元素之间的关系，以及对这些数据元素进行操作和访问的方法。
- 解读：更偏向于工程化描述，强调数据存储、访问和操作的方式。
📖 自己的理解
数据结构 = 数据存储方式 + 数据组织方式 + 数据操作方法
- 存储方式：数据在内存或磁盘中的物理存储（如数组连续存储、链表非连续存储）。
- 组织方式：数据之间的逻辑关系（如线性结构、树形结构、图结构）。
- 操作方法：如何增删改查数据（如栈的
push/pop、哈希表的get/set）。
我们知道，计算机中数据量非常庞大，如何以高效的方式组织和存储呢?
例如：一个庞大的图书馆中存放了大量的书籍，我们不仅仅要把书放入，还应该在合适的时候能够取出来。
图书摆放要使得两个相关操作方便实现：
- 操作 1：新书怎么插入？
- 操作 2：怎么找到某本指定的书？
图书各种摆放方式：
- 方法 1：随便放
- 操作 1：哪里有空位放哪里。
- 操作 2：找某本书，累死。
- 方法 2：按照书名的拼音字母顺序排放
- 操作 1：新进一本《阿 Q 正传》， 按照字母顺序找到位置，插入。
- 操作 2：二分查找法。
- 方法 3：把书架划分成几块区域，按照类别存放，类别中按照字母顺序
- 操作 1：先定类别，二分查找确定位置，移出空位。
- 操作 2：先定类别，再二分查找。
结论：
- 解决问题方法的效率，跟数据的组织方式有关。
- 计算机中存储的数据量相对于图书馆的书籍来说数据量更大，数据更加多。
- 以什么样的方式，来存储和组织我们的数据才能在使用数据时更加方便呢?
- 这就是数据结构需要考虑的问题。
常见的数据结构较多：
- 每一种都有其对应的应用场景，不同的数据结构的不同操作性能是不同的。
- 有的查询性能很快，有的插入速度很快，有的是插入头和尾速度很快。
- 有的做范围查找很快，有的允许元素重复，有的不允许重复等等。
- 在开发中如何选择，要根据具体的需求来选择。
注意：数据结构与算法与语言无关，常见的编程语言都有直接或间接的使用上述常见的数据结构。
类比现实世界
- 数组（Array） → 书架（固定大小，按索引直接拿书）。
- 链表（Linked List） → 火车车厢（每节车厢连接下一节，只能顺序访问）。
- 栈（Stack） → 叠盘子（后进先出，LIFO）。
- 队列（Queue） → 排队买票（先进先出，FIFO）。
- 哈希表（Hash Table） → 字典（通过关键词快速查内容）。
- 树（Tree） → 公司组织架构（CEO → 部门 → 员工）。
- 图（Graph） → 社交网络（用户是节点，好友关系是边）。
算法（Algorithm） 是解决特定问题或完成特定任务的明确、有限的步骤逻辑。它描述了如何将输入数据转换为期望的输出结果，并确保在有限步骤后终止。
算法可以用多种方式进行描述，包括以下几种常见的描述方式：伪代码、流程图、程序代码以及自然语言等。
算法应具备以下特点：
- 确定性：算法的每一步都应该明确且唯一，不会产生歧义。
- 有限性：算法应该在有限的步骤内完成，不会陷入无限循环。
- 输入：算法应该有输入，它接受零个或多个输入参数。
- 输出：算法应该有输出，它产生零个或多个输出结果。
- 可行性：算法应该是可行的，也就是说它可以被计算机或其他计算设备实现。
- 有效性：算法应该在合理的时间内完成，不会消耗过多的计算资源。
设计和分析算法是计算机科学的重要领域之一。通过选择和设计合适的算法，可以提高程序的性能、节约资源，并解决各种计算问题。算法的效率和正确性是评估算法优劣的重要标准，常用的衡量指标包括时间复杂度、空间复杂度、算法的正确性和可读性等。
问题描述：上海和杭州之间有一条长度为 1,000,000 米 的高架线，其中 1 米 出现故障。如何设计一个高效的算法，快速定位故障点？
📖 算法思路
- 从高架线的起点（上海）开始，逐米检查，直到找到故障点。
- 最坏情况：故障点在终点（杭州），需检查 1,000,000 次。
- 平均情况：故障点随机分布，平均需检查 500,000 次。
📖 时间复杂度：O(N)，其中 N = 1,000,000（线性增长）。
📖 缺点：效率极低，尤其当 N 很大时（如百万级数据）。
📖 算法思路
- 初始化：
- 起点
left = 1，终点right = 1,000,000。
- 起点
- 循环直到找到故障点：
- 计算中点
mid = (left + right) / 2 - 检查
mid处是否有故障：- 有故障 → 故障点在左半部分，更新
right = mid - 1。 - 无故障 → 故障点在右半部分，更新
left = mid + 1。
- 有故障 → 故障点在左半部分，更新
- 计算中点
- 终止条件：
- 当
left > right时，left即为故障点。
- 当
📖 时间复杂度
O(logN)，其中 N = 1,000,000。
计算：$\log_2^{(1,000,000)}≈20 （因为2^{20} = 1,048,576）$
最多只需 20 次 检查即可定位故障点！
📖 优势：效率远超线性查找，尤其适合大规模数据。
| 算法 | 最坏情况检查次数 | 时间复杂度 |
|---|---|---|
| 线性查找 | 1,000,000 | |
| 二分查找 | 20 |
结论：
- 二分查找比线性查找 快 50,000 倍（1,000,000 vs. 20）。
- 算法选择直接影响性能，尤其在数据量大的场景下。
算法主要用于解决以下问题：
- 搜索和排序：查找数据、按规则排序（如二分查找、快速排序）。
- 图算法：最短路径（Dijkstra）、最小生成树（Prim/Kruskal）。
- 数值计算：解方程、优化问题（如梯度下降）。
- 字符串处理：匹配（KMP）、压缩（哈夫曼编码）。
- 图像/信号处理：滤波、压缩（JPEG/MP3）。
- AI/机器学习：分类（SVM）、聚类（K-Means）。
- 网络通信：路由协议（OSPF）、流量控制（TCP拥塞算法）。
排序算法是笔试中经常出现的
- 简单排序（基础）
- 冒泡排序：相邻元素两两比较交换。
- 选择排序：每次选最小元素放到已排序末尾。
- 插入排序：逐个将元素插入已排序序列。
- 高级排序（高效）
- 希尔排序：分组插入排序，逐步缩小组距。
- 快速排序：分治思想，选取基准分区递归排序。
- 其他排序（扩展）
- 归并排序、堆排序、计数排序、基数排序、桶排序等。
重点掌握：
- 简单排序的原理和代码实现。
- 快速排序的分区思想（笔试高频）。
算法分析是评估算法性能的科学方法，主要关注：
- 时间复杂度：算法执行时间随输入规模的增长趋势。
- 空间复杂度：算法额外内存消耗随输入规模的增长趋势。
算法分析的目的是比较算法优劣，选择最优解，优化资源使用。
关键分析方法
| 方法 | 说明 | 示例 |
|---|---|---|
| 时间复杂度分析 | 用大O符号表示最坏情况下的时间增长趋势 | 快速排序：O(nlogn) |
| 空间复杂度分析 | 衡量算法运行所需的额外存储空间（不含输入数据本身） | 归并排序：O(n) |
| 最优性分析 | 判断算法是否能得到理论最优解 | Dijkstra算法（最优路径） |
| 平均情况分析 | 考虑所有可能输入的平均性能 | 哈希表查找：平均O(1) |
通过算法分析，我们可以预测算法的运行时间和所需资源，为选择合适的算法和优化算法提供依据。
时间复杂度定性地描述算法的运行时间，首先我们来看一组示例：
function func1() {
console.log('Hello!'); // 执行1次
return 0; // 执行1次
}如果调用1次函数 func1 ，内部语句会分别执行1次，也就是这个函数内部总共执行了两次语句。
我们在看另外一个函数：
function func2(n) {
for(int i = 0; i < n; i++) {
console.log(i);
}
return 0;
}其中：
int i = 0：执行1次i < n：执行 n + 1 次i++：执行 n 次console.log(i)：执行 n 次retrun 0：执行1次
所以，调用1次函数 func2，内部语句总共执行了
一段代码的总执行次数，会用
- 调用1次函数
func1：$T(n) = 2$ - 调用1次函数
func2：$T(n) = 3n + 3$
其中，n 是输入数据的大小或者是输入数据的数量，而 T 是在输入数量为 n 的时候，这一段代码的总执行次数。
但是作为衡量代码的执行速度的依据，当代码比较多的时候，使用
提示：时间复杂度的计算，如果遇到了条件分支语句，以运行时间最长的分支作为时间复杂度的一句。
接下来思考，$T(n)$ 如何得出时间复杂度（推导大O表示法的方式）？
- 如果
$T(n) = 常数$ ，那么时间复杂度可以直接估算为$O(1)$ 。 - 如果
$T(n) = 常数 * n + 常数$ ，可以直接省略加号后面的常数，然后第1部分的常数可以直接估算为1，所以时间复杂度为$O(n)$ 。 - 对于多项式，我们只需要保留
$n$ 的最高次项，再结合前面两条规则即可，比如$T(n) = 5n^3 + 6n^2 + 1$ ，其时间复杂度为$O(n^3)$ 。
不过这样表示时间复杂度并不完整，我们还需要加上大写字母 O，像这样子表示：$O(1)，O(n)，O(n^3)$。
这种方法被称之为：大O表示法
根据上述规则可以推断出：
- 调用1次函数
func1的时间复杂度为：$T(n) = 2 → O(1)$； - 调用1次函数
func2的时间复杂度为：$T(n) = 3n + 3 → O(n)$；
总结：时间复杂度的表示方法就是：$T(n)$ 是不是常数？
- 是：时间复杂度为
$O(1)$ ； - 否：时间复杂度为
$O(保留T(n)的最高次项并且去掉最高次项的系数)$ ；
下面是对常见时间复杂度的一个总结：
| 描述 | 增长的数量级 | 说明 | 举例 |
|---|---|---|---|
| 常量阶* | 普通语句 | 将两个数相加 | |
| 对数阶* | 二分策略 | 二分查找 | |
| 线性阶* | 一层循环 | 找出最大元素 | |
| 线性对数阶* | 分治思想 | 归并排序 | |
| 平方阶* | 双层循环 | 检查所有元素对 | |
| 立方阶 | 三层循环 | 检查所有三元组 | |
| k次方阶 | k层循环 | - | |
| 指数级别 | 穷举查找 | 检查所有子集 |
时间复杂度从低到高依次为： $$ O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) $$
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。
程序执行时所需存储空间包括以下两部分。
（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用 f(n) 表示
$$
S(n) = O(f(n))
$$
其中 n 为问题的规模（或大小），S(n) 表示空间复杂度
！Tips：通常来说，只要算法不涉及到动态分配的空间，以及递归、栈所需的空间，空间复杂度通常为
0(1)。一个一维数组a[n]，空间复杂度O(n)，二维数组为O(n^2)。
1）简单性
- 含义：算法简单；程序结构简单
- 好处：容易验证程序正确性；便于程序调试
！Tips：简单的算法效率不一定高，要保证一定效率的前提下力求得到见到的算法。
2）最优性
- 含义：指求解某类问题中效率最高的算法。
- 我们说：在最坏情况下，如果没有其他我们学过的算法比这个算法执行更少的基本步骤，那么这个算法就是最优的。
3）两种最优性
-
最坏情况下最优：
设A是解某个问题的算法，如果在解这个问题的算法类中没有其他算法在最坏情况下的时间复杂性比A在最坏情况下的时间复杂性低，则称A是解这个问题在最坏情况下的最优算法。
-
平均情况下最优：
设A是解某个问题的算法，如果在解这个问题的算法类中没有其他算法在平均情况下的时间复杂性比A在平均情况下的时间复杂性低，则称A是解这个问题在平均情况下的最优算法。
| # | 公式 | 例子 |
|---|---|---|
| 加法交换律 | ||
| 加法结合律 | ||
| 乘法交换律 | ||
| 乘法结合律 | ||
| 乘法分配律 | ||
| 减法的性质 | ||
| 减法的性质 |
- 正数：比0大的数（符号：
+，可省略） - 负数：比0小的数（符号：
-） - 0既不是正数，也不是负数
- 非正数：0和正数（即
$>= 0$ 的数） - 非负数：0和负数（即
$<= 0$ 的数）
加法运算：
$(-a) + (-b) = -(a + b)$ $(-a) + b = b + (-a) = b - a = -(a - b)$
减法运算：
$(-a) - (-b) = (-a) + b = b + (-a) = b - a = -(a - b)$ $(-a) - b = (-a) + (-b) = -(a + b)$ $a - (-b) = a + b$ $0 - a = -a$
乘法运算：
$(-a) \times (-b) = a \times b$ $(-a) \times b = - (a \times b)$
提示：同号相乘等于正数，异号相乘等于负数
除法运算：
$(-a) \div (-b) = a \div b$ $(-a) \div b = -(a \div b)$
提示：同号相除等于正数，异号相除等于负数。
总结：负负得正
-
$a$ 和$-a$ 互为相反数-
$+2$ 的相反数是$-2$ -
$-2$ 的相反数是$+2$ -
$0$ 的相反数是$0$
-
- 相反数的运算只需要在前面加一个
-即可。
- 绝对值表示方法：$|a|$
- 如果
$a >= 0, |a| = a$ - 如果
$a < = 0, |a| = -a$
- 小数：$1.2$
- 分数：$\frac{1}{2}$
- 百分数：$18%$
分数转小数：
$\frac{a}{b} = a \div b$
百分数（百分率、百分比）推导：
$\frac{59}{100} = 59 \div 100 \times 100% = 0.59 \times 100% = 50%$
我们知道：$3 + 3 + 3 + 3 + 3 = 3 \times 5 $
对于乘法来说，也是可以简化的，比如：
-
$3 \times 3 = 3^2$ （3的平方） -
$3 \times 3 \times 3 = 3^3$ （3的立方） $3 \times 3 \times 3 \times 3 \times 3 = 3^5$
我们知道，$5^2 = 25$，反过来，我们要求几的平方是 25，如：
求
除了2次方根以外，还有3次方根、4次方根等等，如：
$\sqrt[3]{27} = 3$ $\sqrt[4]{625} = 5$
- 除了
$0$ 之外的所有数的零次方都是$1$ ，即$n^0 = 1$ -
$n^{-m} = \frac{1}{n^m}$ ，如：$2^{-3} = \frac{1}{2^3}$ -
$a^{\frac{m}{n}} = \sqrt[n]{a^m}$ ，如：$a^{\frac{1}{2}} = \sqrt{a}$，$a^{\frac{1}{3}} = \sqrt[3]{a}$ -
$a^m \times a^n = a^{m + n}$ ，如：$2^3 \times 2^1 = 2^{3 + 1} = 2^4 = 16$ -
$a^m \div a^n = a^{m - n}$ ，如：$2^3 \div 2^1 = 2^{3 - 1} = 2^2 = 4$ -
$a^mb^m = (ab)^m$ ，如：$3^2 \times 4^2 = (3 \times 4)^2 = 144$ $\sqrt{0} = 0$ - 负数不能开平方根
一个正整数的阶乘是所有小于及等于该数的正整数的积，并且 0 的阶乘为 1。自然数 n 的阶乘写作：$n!$
举个具体的例子，5的阶乘写作：$5!$，其表示：$5 \times 4 \times 3 \times 2 \times 1 = 120$
区间就是一堆数组成的范围，它的表示方法有四种：假设
-
$[a, b]$ →$a \leq x \leq b $ -
$(a, b]$ →$a < x \leq b $ -
$[a, b)$ →$a \leq x < b $ -
$(a, b)$ →$a < x < b $
什么是对数？如果 a 和 b 具体的数值，需要求 ? 是多少？为了方便表示，我们可以使用对数：
$$
? = log_ab
$$
叫做：以 a 为底，b 的对数。其中 a 叫做 底数，b 叫做 指数。