讲解（上）在线视频

这一节，我们来学习算法分析与度量

首先，如何来衡量一个算法的效率

大家能想到的最简单的方式，肯定是测量

我们可以用编程语言，将算法写成真正的程序

然后放到一台电脑上去跑

在这个程序的最开头和最末尾

加上两条取时间的语句

把这两个时间相减

就是这个算法

所耗费的时间

但是这种方式

有几个问题

第一个，先要编写成程序

因为前面说过，算法是不能运行的

要先写成程序

编完程才能跑

第二

它依赖于你所使用的编程语言

甚至是编译器自身的效率

有些编程语言

比如C、C++

它的运行效率是明显高于Java

Python这样的编程语言的

第二个

同一种编程语言根据采用的编译器不同

产生的机器代码的执行效率可能也不一样

所以

如果以测量的方式来衡量算法效率

测出来的结果往往是不太客观的

跟编程语言、编译器相关

另外

它还依赖于具体的硬件

把同一个程序放到一台

现在最新的计算机上跑，跟放到一台十年前的计算机上跑

得到的运行时间肯定也是不一样的

也就是说，这时候程序是受到CPU

甚至是GPU

因为有的程序可能会用到显卡

的加速功能，内存的容量、速率

还有I/O性能等等

总之，硬件也影响了你的测量结果

还有某些偶发因素

对测量结果的影响也比较大

比如，就算在同一台机器上

分别跑两个算法

跑第一个算法的时候

操作系统可能比较繁忙

CPU占用率比较高

或者I/O设备占用率比较高

最后导致算法跑的时间比较长

而第二次跑的时候

CPU比较空闲

也没有什么I/O

得到的时间比较短

那你能说第一个算法要比第二个算法执行的要慢一些吗

这个也不一定

总之

通过测量的方式

它依赖于很多

除算法之外的一些因素，导致并不客观

而第二种方式，是通过人脑分析的方式

那人脑分析，分析什么呢

分析算法当中基本步骤的总的执行次数

因为是人脑分析算法

不需要写程序

而且这个结果

是不受算法之外的任何因素影响的

下面，我们介绍一个很重要的概念

时间复杂度

首先

来看算法的总的执行次数

刚才说了

我们可以先分析算法当中的基本步骤

很可能算法当中的基本步骤会执行很多次

因为有循环

那这样

我们先统计

算法当中

基本步骤的总的执行次数

这个执行次数，肯定是关于问题规模n的一个函数

我们集成F(n)

这里的n

是指问题的规模

简单来说

就是算法要处理的数据量

比如，要对10个整数进行排序

从大到小或者从小到大

那么，这里的n就是指10

要对10000个数据排序

这里的n就是指10000

通常情况下

F是增函数

因为绝大多数情况下，要处理的数据量越多

算法的

总的执行次数肯定就越多

所以F(n)是一个增函数

假设存在一台超脑能运行算法

我们之前讲了，测量的方式是通过电脑来测量，分析的方式

是通过人脑来分析算法当中的基本步骤

现在，假设有一台超脑能够运行算法

注意，算法是不能被计算机运行的

我们现在假设有一台超脑能运行算法

并且，其执行算法中各种基本步骤所耗费的时间是一个常量

我们认为算法当中的基本步骤在超脑上执行的时间是一个常量

这样，总的算法执行时间就等于总的基本步数

F(n)乘上一个常量c

c是每一个基本步骤所耗费的时间

我们把它记成大O——关于F(n)的一个函数

我们记成大O

因为T(n)=c×F(n)

我们可以说T(n)是正比于F(n)的

所以，可以用总的基本步数F(n)来衡量算法的总的执行时间

尽管总的基本步数的单位是次

或者说步，但T(n)的单位，如果是时间的话

可能是秒、毫秒、甚至微秒

但这两者是成正比关系的

所以，我们可以用F(n)来衡量总的执行时间

我们称O(F(n))为大O表示法

这个大O表示法

就是时间复杂度

它是关于算法当中基本步骤的总的执行次数的一个函数

那如何确定算法的基本步骤呢

我们现在来看一个具体的例子

这个函数sum

它对数组a当中的n个元素进行求和

算法总体上是由一个循环构成的

对于这样的语句

是否认为是基本步骤呢

对于循环外的东西

我们通常不认为它是基本步骤

当n足够大的时候

这个算法耗费的时间是在这个循环上

所以

我们把这个循环的循环体当作基本步骤

至于循环外面的变量声明

初始化这样的语句，以及函数的返回语句

我们并不认为是基本步骤

还有，嵌套最深的基本步骤的行为

代表了整个算法的行为

举个例子

假设现在有一个算法

它是由两个并列的for循环构成的

其中，第一个for循环是单重的for循环

第二个for循环是一个双重的for循环

那这个算法

它的行为主要取决于嵌套最深的这个循环

它里面语句的行为。比如，第一个for循环

它里面做的是一个累加的操作

而第二个for循环的内层for循环，做的是一个累乘的操作

那这个算法总体上做的事情就是一个累乘的操作

嵌套最深的基本步骤的行为代表了整个算法的行为

下面我们来看，如何计算基本步骤的总的执行次数F(n)。先来看第一个程序

第一个程序没有循环

那么它跟问题规模n无关

像这样的变量声明

和赋值语句

我们通常不认为是基本步骤

所以，只有这一条，它的F(n)是1。再看第二个程序

i从0开始

i到n-1，一共执行n次

所以，它的F(n)是n。再看第三个程序，i也是从0开始，到n-1

但是for循环的

第3个表达式是自增2

我们列举一个具体的n值

比如，n是偶数8

那么，i能取到的值

是0、2、4、6

一共4个

如果是奇数

假设是7，这时候i的取值

也是0、2、4、6

一共4个

所以，我们分析一下可以发现，这个循环体它的执行次数

应该是n/2向上取整

比如，n是8，能整除

那就是4，7不能整除

那就是3.5向上取整，也就是4

现在我们来看第四个程序

第四个程序

总体上来说是由两个并列的for循环构成的

其中，第一个for循环的i从0开始

i小于n

最后一个值是n-1

这里有2行语句

一共执行2n次

第二个for循环

i从n开始，i>0

每一次，i是自除2的

如果n

是2的整数次方

比如8

那i能取到的值是8、4、2、1

注意不能取到0

因为这地方没有等号

一共是4次

如果n是7呢

也就是不是2的整数次方

这时候，i能取到的值是7、3、1

同样不能到0

一共3次

所以，通过分析

我们可以发现，下面这个for循环

它的F(n)，应该是log(n)向下取整

加1

比如8

那是3+1，是4

如果是7

那是2点几向下取整，是2+1，是3

所以，总的F(n)应该是2n

加上log2(n)向下取整

加1

再看

第五个程序，第五个程序

只有一个for循环，i从0开始

i到n-1

循环体是一个

if-else语句

如果当前元素a[i]等于0

那么，一个变量加1。else，也就是a[i]不等于0

那我们再继续区分

如果a[i]大于0，这个变量加一；小于0

这个变量加1

截止到目前为止

在分析F(n)的时候

我们并没有关心一个算法

到底执行了哪些方面的功能

也就是说

一个算法到底做了什么样的事情，我们并不关心，我们只关心这个算法里面的循环结构

因为我们这里只计算F(n)

而不是分析算法是做什么事情

回到这个程序

我们会发现

无论a[i]的值是多少

这3个自增语句只会执行其中的一条

而且必须执行一条

所以，外层循环0到n-1，一共执行n次

那么，这个算法的F(n)也是n

再看最后一个程序段

总体上由两个for循环构成

第一个for循环，i从0到n-1

这里一共执行n次；第二个for循环，外层循环i从0到n-1

一共n次

内层循环j从0到i

注意，内层循环的执行次数是跟外层循环变量i有关的

我们可以来画一下

如果外层循环i

取0

取到第一个值

内层循环j从0到0，执行1次；外层循环i取1

因为外层循环

每次是i++

i取1，内层循环j从0到1，一共执行2次；外层循环i取2，j从0到2，一共3次。会发现，内存循环

的执行次数总是比外层循环的变量i多1

由此可见

外层循环取到最后一个值

n-1的时候

内层循环执行的次数应该是n

所以，下面这个双重循环

它的总的执行次数应该是1累加到n

那么，总的F(n)应该是

n + n(n+1)/2

我们再来看看函数的增长率与时间复杂度的近似表示

这个图给出了典型的

不同的时间复杂度

它们的

增长曲线

很容易看出，这些曲线呈下面的一些大小关系

当n比较大的时候

需要注意，尽量不要让设计出来的算法

它的时间复杂度包含指数及以上阶函数项的算法

也就是说，尽量让设计的算法的时间复杂度是这些时间复杂度

而不要出现指数函数

因为，当n比较大的时候

指数函数的增长率比前面的这些函数要高得多

n增长一点点

可能时间复杂度就要提升很多很多倍

所以，我们尽量不要设计出包含指数阶函数项的算法

现在，给出一个具体的时间复杂度

假设是这个

会发现，当n比较大的时候

这些灰色的项

也就是低阶项，它们对T(n)的贡献几乎可以忽略不计

另外

最高阶项的系数

也可以忽略不计

所以这时候，我们就将这个时间复杂度认为是约等于

O(n^3)

这是一种大O的近似表示

因为，当n很大的时候

那些低阶项，包括系数

对T(n)的贡献，都比这一项本身

最高阶项本身要低得多

所以可以忽略掉

另外

如果T(n)跟n无关

跟问题规模n无关

仅仅包含常数项

那么这时候，无论基本步骤执行的是1次、2次、10次、100次、10000次

我们都简化成O(1)

都认为是1次

因为，它跟问题规模n是无关的