【原创连载】算法素颜（第3篇）：KO掉大O不再是菜鸟的梦——时间

2019-03-24 本文已影响14人 cubie_zhou

创作时间：2019-03-23

作者：周林

周林的简书主页

周林的CSDN博客主页

周林的知乎主页

在本系列第1篇《走下神坛吧！算法》中提到了：计算复杂度分为时间复杂度与空间复杂度。本篇文章来讲讲时间复杂度。

如何度量时间复杂度

时间复杂度由所消耗的时间决定。所消耗的时间由硬件与软件共同决定。在同一硬件条件下，所消耗的时间由软件决定。

通常意义上的算法指的是软件算法，所以在谈论时间复杂度时，聚焦软件的时间开销。

软件的时间开销 = 软件各组成部分的时间开销之和。

软件最基本的组成部分是语句（或者微观意义下的指令）。

注：因为在同一硬件条件、特定的编程语言环境下，基本语句由多少条指令构成、运行的模式都是固定的，所以直接以语句作为基本考察单位即可。

整体等于各部分之和

对大部分编程语言而言，基本语句无外乎以下两种：

1. 读写语句

2. 比较语句

注：条件语句(if-else)、循环语句(while/for)在这里都不算基本语句，而被看作复合语句。

原因如下：

对于条件语句，一般形式如下：

if (xxx) { // 这条语句相当于先运行比较语句（比较xxx与true的值），

// 然后根据比较结果，运行aaa（aaa可以是一个简单语句，也可以是复合语句）

aaa；

} else if (yyy) { // 这条语句相当于先运行比较语句（比较yyy与true的值），

// 然后根据比较结果，运行bbb（bbb可以是一个简单语句，也可以是复合语句）

bbb;

}

对于循环语句，一般形式如下：(为简单起见，这里只做while的示例，其他循环类型依此来推)

while (xxx) { // 这条语句相当于先运行比较语句（比较xxx与true的值），

// 然后根据比较结果，运行bbb（aaa可以是一个简单语句，也可以是复合语句）

// 再次运行比较语句（比较xxx与true的值）判断是否出循环体

aaa；

}

将基本语句的时间开销看作“单位1”，那么整个程序的时间开销就是所有这些“单位1”之和。

推论3.1:

假设程序结构L由n个子结构Li组成，即：

 $L = \sum_{i=1}^{n}{Li}$

那么运行L的整体时间开销T(L)为：

$T(L) = T(\sum_{i=1}^{n}{Li})=\sum_{i=1}^{n}{T(Li)}$

T(L) = f(n)

来看几个例子：

int i = 10; // 赋值语句，属于基本语句，所以时间开销 = 1

a > b; // 比较语句，数据基本语句，所以时间开销 = 1

if (a > b) { // 条件语句，属于复合语句。它包含了一条比较语句和一条赋值语句，所以时间开销 = 1 + 1 = 2

c= 9;

}

再来看一个复杂一点的：

int buf_size = input_array.size;

for (i = 1; i < buf_size; i++) {

p = q + 1;

if (p > i) {

break;

}

整个程序结构L由一条赋值语句（记为J）和一个循环体（记为K）组成，则：L = J + K （式3.1）

循环体K由一条赋值语句X和一个条件语句Y组成，循环次数n在最坏情况下等于buf_size。所以在最坏情况下：

K = n(X + Y) （式3.2）

代入式3.1，得到：L = J + n(X+Y) （式3.3）

根据推论3.1，从式3.3可得到：

T(L) = T(J) + T(n(X + Y)) = T(J) + nT(X + Y) = T(J) + n(T(X) + T(Y)) (式3.4)

因为J, X为赋值语句，属于基本语句，所以T(J) = T (X) = 1

因为Y为简单条件语句，T(Y) = 2

如果buf_size = 10，那么n = 10

将T(J), T(X), T(Y), n代入式(3.4)得到： T(L) = 1 + 10 x (1+2) = 31

从上面的例子可以看出：

(i) n不同，T(L)的值就不同；

(ii) n越大，T(L)的值也越大；

(iii) n等于buf_size，后者是由输入input_array的规模决定的

所以，可以看出：T(L)与输入规模相关。用数学的语言来描述就是：整体时间开销是一个关于输入规模因子的函数。

用数学表达式表示就是：T(L) = f(n)

T= f(n)的现实意义是什么

f(n)既然是个函数，那么由高中数学知识可知，f(n)的形式有很多种，如：

$f(n) = C$

$f(n) = n^{2}$

$f(n) = log _2n$

$f(n) = a^n$

$f(n) = a_{1}n^{k} + a_{2}n^{k-1} + a_{3}n^{k-2} + ... + a_{k-1}n^{2} + a_{k}n + b$

不同形式的f(n)，在n增加的时候，T增加的速度不同。

每一种f，对应一种算法，所以：

推论3.2:

T表示在同等输入规模（即n一定）的情况下，不同算法的时间开销。

T的增加速度越快，对应算法的时间开销越大，也就表示该算法越复杂。

“两种算法的复杂度在一个量级”到底是个什么鬼

考虑T1 = 2n 和 T2 = n。

很显然，在n固定的情况下，T1/T2 = 2。即：同等输入规模下，第一种算法的时间开销是第二种算法时间开销的2倍。

这种复杂度关系总是常数倍的，即使n取无穷大也是。用数学语言表示就是：

$\lim_{n \rightarrow \infty}{\frac{T_{1}}T_{2}} = C$

从而，我们得到一个关键结论：

推论3.3:

两种算法的复杂度在同一量级等价于

$\lim_{n \rightarrow \infty}{\frac{T_{1}}T_{2}} = C$ （其中C为常数）

聪明的你肯定会问到：如果n趋向无穷大的时候，T1/T2不是常数呢？如果不是常数，那么通常是一个关于n的表达式，随着n的增加，值也增加。这表示T1/T2也将趋向无穷大。用数学术语表达就是“发散”。

我们称这种况下，两种算法不在同一复杂度量级。

推论3.4:

算法1比算法2的复杂度量级高等价于

$\lim_{n \rightarrow \infty}{\frac{T_{1}}T_{2}} = \infty$

大O登场

通常比较算法复杂度，只用比较量级即可。量级用O()表示。

O()定义：

(i) 如果算法T1与算法T2的复杂度在同一量级，那么O(T1) = O(T2)

(ii) 如果算法T1比算法T2的复杂度量级高，那么O(T1) > O(T2)

(iii) 如果算法T1比算法T2的复杂度量级低，那么O(T1) < O(T2)

我们来看一个例子：

$T_{1} = a_{1}n^{k} + a_{2}n^{k-1} + a_{3}n^{k-2} + ... + a_{k-1}n^{2} + a_{k}n + b$

$T_{2}= n^{k}$

比较T1与T2的复杂度量级：

$\lim_{n \rightarrow \infty}{\frac{ a_{1}n^{k} + a_{2}n^{k-1} + a_{3}n^{k-2} + ... + a_{k-1}n^{2} + a_{k}n + b}{n^{k}}} = a_{1}$

根据推论3.3得到：T1与T2处于同一复杂度量级。

根据上述O()的定义： $O(T_{1}) = O(T_{2})$

这里其实蕴含了一个非常实用的结论：

推论3.5:

算法复杂度的大O表示可以简化为该算法最高阶部分的复杂度的大O表示。

根据高等数学知识，我们可以得到：

$O(a^n) > O(n^k) > O(nlog_2n) > O(n) > O(log _2n) > O(1)$

写在最后的话

大O表示法最早由德国数论学家保罗·巴赫曼（英语：Paul Bachmann）在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。而这个记号则是在另一位德国数论学家艾德蒙·朗道（英语：Edmund Landau）的著作中才推广的，因此它有时又称为朗道符号（Landau symbols）。

大部分的算法或者复杂度理论的书籍，在介绍大O时，要么过于数学形式化，要么过于感性非严格化。本篇文章旨在用最少的数学知识、启发式行文方式、全新的原创视角，为读者构建一个清晰、严格的时间复杂度概念。

相信看到这里，以后再面对时间复杂度和大O，你一定信心满满了：）

本原创系列同步在以下自媒体上更新，敬请关注：

CSDN: https://blog.csdn.net/jintianyishiyeai/

知乎：https://www.zhihu.com/people/cubiezhou2017