- JavaScript 算法与数据结构
- 傅里叶级数动画
- https://github.com/krahets/hello-algo
- https://bbycroft.net/llm
- http://zh.lucida.me/blog/on-learning-algorithms/
- https://github.com/labuladong/fucking-algorithm
- https://juejin.cn/post/6913884259388227598
- JavsScript算法和数据结构
- https://me.guanghechen.com/post/game/sudoku/
- https://www.zhihu.com/question/351130108
- https://visualgo.net/enm
- https://juejin.cn/post/6844903519632228365
- 数据结构与算法（一）：https://apprz8zztzy8571.h5.xiaoeknow.com/v1/course/column/p_610384cce4b0bf642fffbbcc?type=3
- 数据结构与算法（二）：https://apprz8zztzy8571.h5.xiaoeknow.com/v1/course/column/p_610387b5e4b0a27d0e3766ba?type=3
- 数据结构与算法（三）：https://apprz8zztzy8571.h5.xiaoeknow.com/v1/course/column/p_610388a2e4b0bf642fffbd24?type=3
- 漫画：图的 “最短路径” 问题
排序
冒泡排序 选择排序 插入排序 归并排序
JS 快排
Array.prototype.quickSort = function() {
if (this.length < 2) {
return this;
}
return [...this.filter(el => el < this[0]).quickSort(), this[0], ...this.filter((el, i) => el >= this[0] && i !== 0).quickSort()];
};
http://blog.csdn.net/k346k346/article/details/50791102
https://www.cnblogs.com/eniac12/p/5329396.html
1
1.2.1 二分法
有序列表
log_2 n
1.2.2 运行时间
线性时间 对数时间
1.3 大O
大O表示最糟的情形
- 二分法
O(log n)
- 简单查找（线性时间）
O(n)
- 快速排序平均情况
O(n * log n)
- 选择排序
O(log n^2)
- 旅行商（排列组合）
O(n!)
2 选择排序
2.2 数组和链表
2.2.1 链表
2.2.2 数组
2.2.3 术语
数组带索引，所以在读取的时候比链表快。
2.2.4 在中间插入
2.2.5 删除
| - | 数组 | 链表 |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 插入 | O(n) | O(1) |
- 随机访问 → 数组
- 顺序访问 → 链表
2.3 选择排序
O(n^2)
3 递归
3.3 栈
是一种数据结构
3.3.1 调用栈
4 快速排序
分而治之（divide and conquer, D & C）著名的递归问题解决方法
4.1 分而治之
1 找出简单的基线条件
2 确定如何缩小问题的规模，使其符合基线条件
D&C 并非可用于解决问题的算法，而是一种解决问题的思路。
4.2 快速排序
基准值 pivot
分区 partitioning
- 选择基准值
- 将数组分成两个子数组
- 对两个子数组快速排序
4.3 再谈大O表示法
合并排序（merge sort）
O(n * log n)
4.3.2 平均情况和最糟情况
5 散列表（hash table）
5.1 散列函数
Python 字典（dict）实现了散列表
5.2.2 防止重复
使用散列表防止重复
5.2.3 用散列表用作缓存 ✖
5.3 冲突
5.4 性能
5.4.1 填装因子
0.7
5.4.2 良好的散列函数
将每个字符都映射到一个素数：a = 2, b = 3, c = 5 … 对于给定字符串，将每个字符对应的素数相加，再除以散列表长度，取余。
6 广度优先搜索
6.1 图简介
最短路径问题（shorter-path problem）
6.2 图是什么
节点，边
图用于模拟不同的东西是如何相连的。
6.3 广度优先搜索
- 从节点A到节点B有路径吗？
- 从节点A到节点B哪条路径最短？
6.3.1 查找最短路径
6.3.2 队列（queue）
先进先出（FIFO）
6.4 实现图
有向图（directed graph） 无向图（undirected graph）
6.5 实现算法
运行时间
O(V + E)
拓扑排序
树
7 戴克斯特拉算法（Dijkstra's algorithm）
1 找出最便宜的节点，即可在最短时间内到达的节点
2 更新该节点的邻居的开销，检查是否有前往他们的更短路径，如果有，就更新开销
3 重复这个过程，知道对途中每个节点都这样做了
4 计算最终路径
7.2 术语
权重（weight）
加权图（weighted graph）、非加权图
环，增加了权重
戴克斯特拉算法只适用于有向无环图
7.3 换钢琴
7.4 负权边
贝尔曼-福德算法（Bellman-Ford algorithm）？
7.5 实现
https://www.cnblogs.com/jiqingwu/p/bubble_sort_analysis.html https://www.cnblogs.com/qiaozhoulin/p/4808285.html https://blog.csdn.net/qq_36470686/article/details/82846427 https://blog.csdn.net/thomasli2017/article/details/77422323