MIT算法导论——第一讲.Analysis of algorithm

时间:2022-01-22 06:43:50

本栏目(Algorithms)下MIT算法导论专题是个人对网易公开课MIT算法导论的学习心得与笔记。所有内容均来自MIT公开课Introduction to Algorithms中Charles E. Leiserson和Erik Demaine老师的讲解。(http://v.163.com/special/opencourse/algorithms.html

第一节-------课程简介及算法分析 Analysis of algorithm

算法分析:关于计算机程序在效率和资源利用方面的理论研究。

第一节课的内容相对来说比较简单,但是大牛就是大牛,能够把抽象的东西说的相当形象,让人过目不忘的同时去思考背后的原理。总结一下,主要有以下几个知识点。

1.算法分析的主要内容是效率,有比效率更重要的吗?当然有,比如正确性、可维护性、可扩展性、健壮性、安全性等等,可以想象得到以前很多在软件工程中谈论到的重要的东西。既然如此,为什么还要进行算法的效率分析呢?在课上老师说了一个很有意思的比方,你认为钱重要还是水和饭重要?当然是水和饭,钱是不能保证人的生存的,但是钱却可以换来水和饭。而算法分析中的“效率”就相当于“钱”,你可以用“效率”来换取其他东西,比如安全性,稳定性等等。它只是一个交换物,但我们,却离不开它。

2.衡量效率的因素。既然效率如此重要,我们用什么因素来衡量一个程序效率的高低呢?运行时间。对于同一组输入,你的程序运行时间比别人的短,就说明你的程序在这组数据集上的效率比别人的高。

对于运行时间,需要考虑的因素有如下三个:

a、数据的输入情况。例如,对于插入排序算法来说,一个已经排好序的序列更容易排序;

b、数据的规模。很显然,短的序列要比长序列更容易排序;

c、找到运行时间上界。一般情况下,我们需要找到这个程序对于最坏的输入数据的情况下,运行时间是多长。毕竟,每个人都想得到一个guarantee。

3.几种分析运行时间的方法T(n)。

Worst-case:(usually) —— 用T(n)来表示算法在输入规模为n时的最大运行时间。它的作用就是你可以用它来给别人做出承诺,即我的算法在最坏的情况下的运行时间也不会超过T(n)。

Average-case:(sometimes)—— 用T(n)来表示算法在所有输入规模为n的序列的运行时间的一个期望值。当然它的前提是假设输入的统计概率分布,也就是说对于一个规模为n的输入数据,它所有的排列方式出现的概率是相等的。

Best-case:(bogus)——而如果你想骗人,用一组极好的数据在一个效率极低的算法上跑,我们称之为算法的运行时间的最好情况,这是不够说服人的。

4.Big Idea——渐近分析。

我们通常所说的运行时间,都会存在一个相对时间与绝对时间的区别。比如在一台巨型机和在一台微机上运行同一个程序,所用的时间显示是不同的。这是我们就需要引入一个更加宏观的概念:渐近分析——对于一个算法的运行时间,忽略那些依赖于机器的常量;忽略所有的低阶项,只分析最高阶项;关注于运行时间的增长,而不仅仅只是运行时间。引入一个助记符号θ(n),举一个例子:如果一个算法的运行时间为:3n^3 + 2n^2 + 4n + 1,那么忽略掉依赖机器的常量1,以及所有的低阶项2n^2、4n,那么这个算法的时间复杂度就为θ(n^3)。

在这里,老师也进行了很形象的说明。如果算法A的渐近时间复杂度是θ(n^3),算法B的是θ(n^2),那么一定存在一个足够大的n,使得当数据规模大于n时,算法B的运行时间要小于A,不管算法A一开始的优势有多么大,不管算法B的渐近复杂度的系数和常数有多么大,都没有用。用这样一个助记符就可以将时间复杂度的分析独立于机器,独立于具体的常数,对我们分析算法将会十分有利。

5.两个例子——插入排序、归并排序

插入排序的思想就是,对于每一个A[i],考虑A[1...i-1]中它的合适的插入位置k,然后将A[k...i-1]依次后移一个位置,把A[i]插入到A[k]的位置即可。

MIT算法导论——第一讲.Analysis of algorithm

上面就是插入排序的伪代码,用缩进代表算法的层次。对插入排序做渐近分析,如下图所示。下面一系列分析过程说明了插入排序的渐近时间复杂度是n^2级别的。

MIT算法导论——第一讲.Analysis of algorithm

所谓归并排序,举个例子,归并排序递归处理的两个表已经有序了,为{2, 7, 13, 20}和{1, 9, 11, 12}。

我们如何合并这两个表呢?这两个表已经是有序的了,我们要找出当前表中剩下的最小元素,这个最小元素一定是在表1的头部或表2的头部,然后取出来,放入总的表中,此时我们取出了1这个元素。那么表2中还剩下3个元素,然后再接着比较表1和表2,找出最小的元素,为2,这样我们依次找下去,便可以将两个有序表合并成一个有序表。如下图所示。

MIT算法导论——第一讲.Analysis of algorithm
下图是归并排序的伪代码以及算法渐近分析。

MIT算法导论——第一讲.Analysis of algorithm

下面我们用递归树的方法来分析这个算法的运行时间,首先写出运行时间的递归表达式:如果我们考虑n>1的情况,T(n) = 2T(n/2) + Cn,其中C为一个常数。画成递归树的形式如下图所示:

MIT算法导论——第一讲.Analysis of algorithm

那么,我们看一下上面第三幅图,第一行的时间和为Cn,第二行的时间和为C(n/2)+C(n/2) = Cn,...,第lgn行的时间的和为θ(n)。其中,lgn为树的高度,简单分析即可得出。

那么一共lgn行,每行时间和为Cn,简单计算即可知这棵递归树的总的时间和(即算法的渐近时间和)为 (Cn)lgn + θ(n),忽略低阶项θ(n),即算法的渐近时间复杂度为θ(nlgn)。

讲到这里,第一节的内容也就快结束了。老师最后给出了一个结论:归并排序能够在效率上当输入规模n增大的时候渐近的超过插入排序,在最坏的情况下。实际上,当n>30以及以上的时候,归并排序的效率就比插入排序的效率要高了。Go test it out for yourself!

关于Introduction to Algorithms更多的学习资料将继续更新,敬请关注本博客和新浪微博Sheridan