数据结构与算法¶
从一个可以手算的问题开始:四项任务到达时间不同,有的还要等其他任务完成,你会怎样决定谁先运行?课程先讲清数据怎么存、操作要付出多少成本,再用队列、堆和图一步步完成这个例子。
如果只会写循环,可以先读数组的五格插入:画出每次搬动后哪一格改变。然后用链表的同一组号码做同样的插入,回头看一列号码变长时,哪些操作会跟着变慢。首次阅读选自己会的一种语言即可,其他语言的代码留作对照。
怎么读¶
| 阶段 | 先掌握什么 | 可以动手做什么 |
|---|---|---|
| 第 1–2 章 | 怎样检查循环每走一步都正确,以及输入变大时开销怎样变 | 找出最早任务,手推循环并估算开销 |
| 第 3–8 章 | 用数组和链表存顺序,用有限格子排队,用号码建目录,按优先级取下一项,再练习搜索和排序 | 改一个操作频率,比较数据结构是否还适合 |
| 第 9–10 章 | 沿连线或箭头访问各个点、找代价最小的路、按依赖排先后 | 在同一张图里分清找路径与满足依赖 |
| 第 11–13 章 | 拆成小题、撤销一次尝试、保存已算的答案、判断能否每次只留一个选择 | 用反例检验选择策略,再做任务调度综合练习 |
初次阅读,能把示例手推一遍,再跑熟悉语言里的实现。读到复杂度时同时写下条件,比如输入是否有序、图中用来表示代价的数字能不能为负、插入位置是否已经找到。实验偶尔会得到相反直觉,原因可能是数据规模、分布或内存访问方式。
原始资料与拓展¶
本笔记中的大部分内容修改自 Hello 算法 项目,原项目由 krahets 创建,并遵循 CC BY-NC-SA 4.0 许可证。这里的改写、删补和新增内容均为个人学习记录与扩展。
下图是原项目的学习地图,可用于对照知识点。
- VisuAlgo 图遍历可逐步观察广度优先遍历和深度优先遍历(BFS 和 DFS,见图的遍历)。
- MIT 6.006 讲义适合在做完小例子后核对条件和证明。
