01 复杂度分析与排序算法
复杂度分析
时间复杂度：程序的运行步数和输入数据的关系。
空间复杂度：程序运行所需要的内存与输入数据的关系。
复杂度的计算
直接算
对于比较简单的程序，我们可以直接计算时间复杂度。
例如下列矩阵乘法的代码：
//O(nmr) ≈ O(n^3)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=r;k++)
c[i][j]+=a[i][k]*b[k][j];
上述代码的时间复杂度为 \(O(nmr)\)，如果 \(m,r\) 和 \(n\) 同阶，那么该代码的时间复杂度也可以记为 \(O(n^3)\)。
均摊
假设一张 \(n\) 个点 \(m\) 条边的无向图，遍历一遍所有的边：
//O(n+m)
for(int i=1;i<=n;i++)
for(auto v:g[x])
......
看似上述代码的时间复杂度为 \(O(nm)\)，但是每条边的 \(u,v\) 最多会被枚举两次，所以时间复杂度为 \(O(n+m)\)。
势能
听了半天，听不懂，不过感觉没啥用，这里放三个博客吧。
主定理
主要用来计算一些递归算法的时间复杂度。
$a \ge 1,b > 1 $ 为常数，\(f(n)\) 为函数，\(T(n)\) 为非负整数，则有以下结果（分类讨论）：
-
若 \(f(n) = O(n^{\log_{b} {a-\epsilon}}),\epsilon > 0\)，那么 \(T(n) = O(n^{\log_{b} {a}})\)；
-
若 \(f(n) = O(n^{\log_{b} {a}})\)，那么 \(T(n) = O(n^{\log_{b} {a}} \log n)\)；
-
若 \(f(n) = \Omega(n^{\log_{b} {a+\epsilon}}),\epsilon > 0\)，且对于某个常数 \(c < 1\) 和所有充分大的 \(n\) 有 \(af(\frac{n}{b}) \le cf(n)\)，那么 \(T(n) = O(f(n))\)。