算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来粗略分析执行效率与数据规模之间的增长趋势关系，越高阶复杂度的算法，执行效率越低。复杂度分析是数据结构与算法的核心精髓，旨在不依赖硬件、宿主环境、数据集的情况下，粗略推导，考究出算法的效率和资源消耗情况。
复杂度分析
在 CPU 的角度看待程序，那么每行代码执行的操作都是类似的，属于如下三种情况：
- 读数据
- 写数据
- 运算
尽管每段代码执行的时间都不一定一样，但在粗略的估计中，可以假设每行代码执行一次所需的时间均是单位时间（unit_time），一个算法的时间耗费就是该算法中所有语句的执行时间之和。
无穷小量与无穷大量的阶
通俗的语言来说：
- \(f(x)=o(g(x))\) 是指：在 \(x\) 取极限的时候，\(f(x)\) 相对于 \(g(x)\) 是可以忽略的小量
- \(f(x)=O(g(x))\) 是指：在 \(x\) 取极限的时候，\(g(x)\) 可以控制/限制住 \(f(x)\)，即 \(f(x)\) 的增长规模/增长率/数量级不可能超过 \(g(x)\) 的增长规模/增长率/数量级
严谨定义：
- 若 \(\lim\limits_{x \to x_0}\frac{f(x)}{g(x)} = 0\)，则表示当 \(x \to x_0\) 时，\(f(x)\) 趋于零的速度比 \(g(x)\) 快。称为当 \(x \to x_0\) 时，\(f(x)\) 关于 \(g(x)\) 是高阶无穷小量，记为 \(f(x)=o(g(x))\)；
- 若存在 \(A > 0\) 使得在 \(x_0\) 的某个去中心领域中，有 \(\left|\frac{f(x)}{g(x)}\right| \leq A\) 成立，则称当 \(x \to x_0\) 时，\(\left|\frac{f(x)}{g(x)}\right|\) 是有界量，记为 \(f(x)=O(g(x))\)；
大 O 表示法
当问题规模增长时， 基本操作次数必定也会增长， 而我们关心的是这个执行次数以什么样的数量级增长。所谓数量级可以理解为增长率。这个所谓的数量级本质上就是算法的渐近时间复杂度（asymptotic time complexity）， 简称为时间复杂度。
一个算法花费的时间与算法中语句的执行次数成正比例，若用语句的执行次数 \(T(n)\)（称为语句频度或时间频度，是问题规模 \(n\) 的一个函数）代表算法的时间复杂度，则可以找到一个满足下式的显式辅助函数 \(f(n)\) ，用于表示时间复杂度： \[ T(n) = O(f(n)) \] 其中：
- \(n\)：表示问题的规模/数据的规模；
- \(T(n)\)：算法中语句的执行次数（称为语句频度或时间频度），代表代码的总执行时间，即时间复杂度；
- \(f(n)\)：辅助函数，满足：当 \(n \to \infty\) 时，存在 \(A\)，使得 \(\left|\frac{T(n)}{f(n)}\right| \leq A\) 成立，即：\(T(n)\) 的数量级不可能超过 \(f(n)\)
常见语句的时间复杂度
in 语句
python 代码常用 in 来判断一个元素是否在 list 中，而对于长度为 n 的不同数据结构，in 语句判断的时间复杂度如下：
- in list : o(n)
- in set : o(1)
- in dict : o(1)
for 语句
一个 for 循环的时间复杂度等于循环次数乘以循环体代码的复杂度；
if-else 语句
if-else 结构的复杂度取决于 if 的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中数量级最大的那个；
常见复杂度量级
当 \(n \to \infty\) 时，有： \[ O(1) < O(\log{n}) < O(n) < O(n\log{n}) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) \]
LeetCode 中数据规模跟要求的算法时间复杂度的对应关系大概为：
| Input Size | Complexity |
|---|---|
| \(10^9\) | \(O(\log{n})\) |
| \(10^6\) | \(O(n)\) |
| \(10^5\) | \(O(n\log{n})\) |
| \(1000\) | \(O(n^2)\) |
| \(30\) | \(O(n^4)\) |
| \(15\) | \(O(2^n)\) |
| \(10\) | \(O(n!)\) |
参考资料
https://www.cnblogs.com/jonins/p/9950799.html
https://www.cnblogs.com/jonins/p/9956752.html