1.6算法分析示例在线视频

同学们大家好，这一节我们通过一些例子来看一下

如何对算法进行分析

第一是矩阵乘法的例子

有a 和b两个n乘n的矩阵相乘

乘的结果是一个n乘n的矩阵c

下面看看矩阵乘法的主要代码段

这段代码中

外层的两个循环为了求出矩阵C中的每个元素

对一个具体的元素c[i][j]的计算来说

是由最内层循环完成的

首先c[i][j]赋初值0

每次循环用矩阵a中第i行第k列的元素和

矩阵b中第k行第j列的元素相乘

并累加到c[i][j]中，经过n次循环，计算出c[i][j]

从这段代码来看，它主要的操作是乘法操作

我们可以用乘法操作的执行次数作为算法复杂性的度量

要求的矩阵c中的元素总共有n乘n个

每个需要n次乘法，所以总的乘法次数是n3方

那么它的时间复杂度就是t（n）等于O(n3)

在一段程序代码中

基本操作总是包含在程序的某一个语句当中

例子中，乘法操作包含在一个赋值语句中

那么对于基本操作执行次数的统计

可以转化为对包含该基本操作的语句执行次数的统计

二者的执行次数是一样的，这就引出了语句频度的概念

语句频度是指该语句重复执行的次数

在后面的算法分析中，我们是以包含基本操作的语句

执行的次数作为算法时间效率的度量

这样更方便一些

例2是一个简单的例子，这个例子当中包含了两个语句

一个自加语句，一个赋值语句

如果我们仅考虑自加语句，那么语句频度是1

时间复杂度是O(1). 如果将赋值语句也看成基本操作

那么语句频度是2. 它的时间复杂度仍然是O(1)

我们称为常量阶

这是时间复杂度的一个量级，并不是说

基本操作只执行一次，而是指在这个算法当中

语句执行的频度是一个常量c

具体的常量C可能很大

只要基本操作执行的次数和问题规模无关，它就是一个常量

例3是一个一重循环的例子

那么循环变量i从1到n

如果把两个语句都看做基本操作的话

语句的频度是2n. 我们可以把系数去掉

它的时间复杂度是O(n)

这样的时间复杂度我们称为线性

例4是一个二重循环的例子

循环控制变量，i和j从1到n

同样把两个语句都看做基本操作

语句执行的次数为2n方.

同样把系数去掉，其时间复杂度是O(n2)

这样的时间复杂度我们称为平方阶

例5也是一个二重循环的例子，稍微复杂一点

外循环i从2到n，内层循环阶的执行次数和

外层循环控制变量i的大小有关

循环控制变量j是从2到i-1， 这段代码中

自加语句执行的频度怎么分析呢？

这里需要我们来做一个展开

考虑i等于2的时候

内存循环中，j赋值2.

这个时候进行循环判断

i-1等于1. 循环的条件并不满足

所以内部的语句是不执行的

考虑i等于3的时候。j赋值2，i -1等于2

循环条件小于等于会满足1次

自加语句会执行1次，j自加后循环条件不成立

内层循环结束，

同理，I等于4的时候

内层循环的语句会被执行2次，依次类推

外层循环最后，当I等于n的时候

内层循环的语句会被执行n-2次

考虑外层循环i从3到n的变化

内层语句执行的频度就是1+2+3一直加到n减2

这就是自加语句执行的总的次数

这是一个等差数列，我们可以直接计算

最终的结果是n平方减3n+2.把低价部分去掉

时间复杂度呢也是O(n2).

这个算法的时间复杂度仍然是平方阶的

例4和例5两段代码中

语句执行的具体次数来说是有差异的

但在做算法时间复杂度估算的时候

我们认为他们是同阶的

在变化趋势上没有本质性的差异

通过上面的例子

我们对算法分析应该有了一个直观的认识

在后续的课程中，我们结合遇到具体算法再来讨论

总结一下，有6种算法的时间复杂度是多项式界的

它们之间的大小关系如屏幕所示

这些时间复杂度的多项式是我们在后续分析中常见的

还有一类算法的时间复杂度是指数阶的

2的n方，n的阶乘，n的n方。我们要注意

多项式时间的算法和指数阶的算法是有明确分界的

当n取得很大的时候

指数时间算法和多项式时间算法

在所需的时间上是非常悬殊的

教材中，图1.7给出了常见时间复杂度函数的增长率图示

大家可以看一下

当问题规模15的时候

2的n方已经无法表示

下面我们通过一个表，直观的看一下

在这个表中，第一行是各种常见的时间增长率的函数

第1列表示问题的规模。从表中我们可以看到

前面4列是多项式时间的复杂度，随着问题规模的增长

语句频度的增长并不是特别显著。最后一列是2的n方

可以看到，随着问题规模的增长

语句频度的变化是巨大的

当问题规模仅仅为32的时候

语句的执行次数就是21亿次之多

可以想象后面的增长是怎样的恐怖

所以，在实际问题中

一般指数时间的算法我们认为是无用的

那我们可以想一下，当问题的规模持续增长的时候

这样的数字是非常可怕的

这样的语句执行频度

实际上已经超出了计算机的计算能力

本节中，我们讨论了算法时间分析的一些方法

主要是围绕程序自身的结构

比如说它是一重循环，二重循环

还是三重循环

实际上，影响算法执行效率的因素还有其它

在有的问题当中，算法中基本操作重复执行的次数

还和要处理的数据对象有关，输入数据的不同

会影响算法执行的效率

下面的例子是一个起泡排序的程序

利用起泡排序算法

对一个待排序的序列进行自小到大的排序

起泡排序的过程是这样的

考察待排序序列第1和第2个元素

如果是逆序，则进行交换

随后考察第2第3个元素

同样，如果是逆序，则进行交换，依次类推

一直考察到序列的第n-1和第n个元素

这个过程称为一趟起泡排序

通过这样一趟起泡排序

序列中最大的一个元素

一定放在了最后一个位置

随后呢，进行第二趟起泡排序

过程和上一趟一样

只不过最后一个元素

就不必考虑了

只考察到第n-1个就可以了

这个过程持续进行，当某一趟排序的过程当中

如果发现整个起泡的过程当中没有交换

也就是说整个起泡的过程当中没有发现逆序的情况

那么，我们就知道待排序序列已经有序

排序算法可以结束了

现在我们假设基本操作是交换

那么我们就考察红色标注的交换语句

a[j]↔a[j+1]执行的频度

我们注意到

这个语句执行的频度和待排序序列的初始状态有关

如果待排序序列初始就是有序的

那么交换，实际上一次都不会执行

也就是说语句的执行次数是0

这种情况

我们称为最好情况下的时间复杂度

最坏情况是初始序列是逆序的情况

交换的次数是n×（n-1）÷2

这是最坏的情况，我们称为最坏情况的时间复杂度

在后续进行算法时间复杂度分析的时候

我们更关注的是最坏情况下的时间复杂度

最坏情况下的时间复杂度给出了

估算算法执行时间的一个上界，也就是说

对这个算法来说，最坏也不过是这个样子了

另外，算法还有平均时间复杂度的概念

我们后面结合具体算法再讨论

本节最后，我们简单的说一下算法的空间效率问题

空间复杂度是对算法在执行的过程当中

所需存储空间的一个度量

空间复杂度s（n）等于O(f(n))

算法执行过程当中，空间的需求一般来说也是

问题规模n的一个函数

在这儿呢

我们就不进一步讨论了

空间复杂度的分析一般而言比较简单

大部分问题当中，算法运行的空间需求

和问题规模一般来说是线性的

伴随存储技术的发展，空间需求的矛盾并不突出

后面的我们一般不进行深入的讨论

同学们

今天的课就到这儿

下节课再见