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))$。