一般来说，程序运行的快慢和机器性能以及程序执行的基本操作数量有关，时间复杂度分析则抛开机器性能单独计算一段代码的基本操作数量。

复杂度定义

假设 n 表示问题的规模，那么一段程序解决这个问题所需操作 f(n) ：

正式定义

说人话

假设我们把 f(n) 和 g(n) 的比较看做是两个数 a 和 b 的比较，那么

性质

1.传递性

显然由于不等式地传递性可以得到复杂度记号的传递性

2.自反性

由于“小O(o)”和"小Ω(w)"要求等号不能成立，所以只有以下三种符号满足自反性。

3.对称性

只有渐进紧确界满足

4.转置对称性

由正式定义易得两组对偶关系

最常见三个

大 O、大Ω 和大 θ是最常用的三个记号，它们的图示说明如下（来自CLRS）：

1.大O是复杂度上界

2.大Ω是复杂度下界

3.大θ是复杂度确界（同时满足1、2）

为什么算法复杂度分析重要

对于问题规模很小的情形，随便选种算法都可以，但当问题规模非常大时（n 很大），那么算法的复杂度随 n 的增长情形就很重要了。下图展示了常见的几种复杂度随问题规模 n 增长的情形。

可以看出随着问题的规模增大 （n ++），不同复杂度曲线分化情形非常明显。当问题规模比较大时，选择一个复杂度低的算法有可能比复杂度高的算法快上亿倍。

复杂度分析

1.一般来说普通的一行代码可以看做O(1)

2.对于循环来说一般为O(n),嵌套循环为O(n^k)

注意此时O不一定可以强化为θ，因为可能存在摊还情况使得上述简要分析不是上确界。

3.当复杂度遇上递归

分治法是算法中一种重要的思想，很多情况下我们都需要把一个问题分解为若干个规模更小的子问题递归求解，这时复杂度怎么分析呢？我们根据问题的划分方式给出两种解决方案。

3.1Master公式

假如子问题是均分得到的，即我们将规模为 n 的原问题，分为 a 个规模为n/b 的子问题进行求解，整合这 a 个子问题耗时O（n^d），那么直接上master公式计算其复杂度。

Master 公式本质上是比较求解子问题和整合子问题结果得到综合结果两个过程的复杂度，占主要部分者是最终问题的复杂度。

非严格证明比较简单，直接递推公式求通项，使用差比数列求和，分类讨论主要成分即可，这里证明就略去了。下面通过几个例子来说明master公式的运用：

（1）归并排序

将排序问题分解为 2 个规模为原来 1/2 的子问题，整合子问题耗时O(n)，即:

那么其符合Master公式第一种情况，所以其复杂度为O(nlog(n))。另外 FFT 的递归求解也符合这一情况。

（2）不好意思我没想出来一个确定性算法符合下面递推公式

假设我们有一个算法复杂度递推公式如下：

不过有些随机算法一般情形的期望复杂度符合上述表达式，例如使用分治法求解序列第 k 大，只需要对问题的一半进行处理，另一半完全可以舍弃。整合只需要O(n)。

这个符合Master公式的第二种情形，所以其复杂度为O(n)。

（3）Strassen 矩阵乘法

将矩阵乘法问题分解为7个规模为原来问题一半的矩阵乘法，顶层整合子问题需要θ(n^2)次操作，则其递推公式可以写作如下形式：

其符合Master公式第三种情况，所以其复杂度为O(n^log(7))≈O(n^2.8)。

3.2归纳法

有些随机性算法不能将问题均分（例如快速排序），此时不能使用Master公式。例如有些随机化算法最差情形满足如下递归公式：

假如我们放缩使得其变为子问题规模一样的递推式，即：

那么此时其符合 Master 公式第三种情形，所以其复杂度为:

这的确是一个上界，但却不是 tight 的上界。因为我们过度放缩了，事实上符合这种递推公式算法的复杂度为O(n)。这需要使用归纳法来证明。

我们猜一个上界，然后使用数学归纳法证明我们的猜想正确：

所以对上述递推公式我们粗略证明如下，假设T(k)<=10C1k（这是一种O(n)复杂度）。

所以其紧上界为O(n)。

总结

本文主要介绍了 5 种复杂度记号并说明了它们的性质。通过直观观察函数增长情况说明了为什么时间复杂度重要。最后介绍了复杂度分析（特别是分治递归算法复杂度）的一些方法。

致谢

本文许多图片来自CLRS！