如何学习算法

学习的步骤

是什么
- 数据结构：一组数据的存储结构
- 算法：操作数据的一组方法
- 数据结构为算法服务，算法要作用在特定的数据结构之上
重点是什么
- 复杂度分析
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
为什么要学
- 修炼自己的内功、锻炼自己的逻辑思维能力
- 成为 top 程序员
怎么学
- 边学边练，适度刷题（python、java、c++、js）
- 多思考、多互动
- 坚持学会、掌握，练习
- 反复三遍

执行算法的时间随数据规模增长的变化趋势
T(n) = O(f(n))
- T(n) 代码的执行时间
- f(n) 代码的执行次数总和
只关注循环执行次数最多的一段代码
加法法则：总复杂度等于量级最大的那段代码的复杂度
- T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
- T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))
常见的时间复杂度
- 多项式量级
  - O(1)，代码中不存在循环、递归语句
  - O(logn)、O(nlogn)，对数阶时间复杂度，以步长做循环
  - O(m+n)、O(m*n)，两个数据的规模决定时间复杂度
- 非多项式量级：O(2n) 和 O(n!)

最好情况时间复杂度（best case time complexity）➡️ 最理想的情况
最坏情况时间复杂度（worst case time complexity）➡️ 最糟糕的情况
平均情况时间复杂度（average case time complexity）
- 加权平均时间复杂度、期望时间复杂度
均摊时间复杂度（amortized time complexity）
- 有一定的前后时序关系
- 大部分情况下时间复杂度都相同，个别情况不同
- 一般情况下，均摊时间复杂度等于最好情况时间复杂度
- 是一种特殊的平均时间复杂度

定义清楚问题
- 调研问题
- 对模糊的需求进行假设，限定要解决的问题的范围
理解隐藏需求
- 需求一般可以分为功能性需求和非功能性需求
- 功能性需求一般来讲是和业务逻辑紧密相关的
- 非功能性需求包括安全、性能、用户体验等
尝试用学过的数据结构解决这个问题
- 尝试对比多种数据结构
- 如果不能直接使用基本数据结构解决，尝试改造数据结构，可以结合多个数据结构的不同特点，使用多个数据结构尝试解决
计算时间、空间复杂度，包括对内存、磁盘的访问

熟知每种数据结构和算法的功能、特点、时间空间复杂度
时间、空间复杂度不能跟性能划等号
- 复杂度不是执行时间和内存消耗的精确值，会忽略低阶、常数、系数
- 处理小规模数据时，代码的执行时间有时不跟时间复杂度成正比
- 对于处理不同问题的不同算法，复杂度没有可比性
算法的选择，一定要根据数据规模来抉择。数据规模小的时候，不必选择高级算法，而是选择简单、易维护、易实现的算法
解决问题的重点在于对需求的调研、理解，理清楚要处理数据的特征与访问方式
区别对待 IO 密集、内存密集、计算密集
- 数据在磁盘上，代码的性能瓶颈可能在磁盘 IO，要尽可能地减少磁盘 IO 的次数
- 数据在内存中，判断代码是内存密集型还是 CPU 密集型
  - CPU 密集型，CPU 计算耗时占大部分，在选择数据结构和算法的时候，要尽量减少逻辑计算的复杂度，如用位运算代替加减乘除等
  - 内存密集型，内存数据的读取耗时占大部分，可以考虑是否能减少数据的读取量，数据是否在内存中连续存储，是否能利用 CPU 缓存预读
使用现有算法，避免重复造轮子
不要漫无目的地过度优化