2006年五月月 发布的文章

算法时间复杂性之渐近法分析基础

在我的评论栏中有人说:"你是程序员?",我可以确定、一定以及肯定地告诉他/她:'我就是一个程序员,如假包换'。也许是最近技术类的blog写得少了,其他类的多写了些,让人家误会了,这也无可厚非。不过我倒是想到这样一个问题:程序员一定要满篇地谈技术么,程序员也有自己丰富多彩的生活呀。好了,切入正题。今天我们谈谈算法时间复杂性的分析。我没系统学过,都是在书上看到的以及MIT算法导论课上听到的。这里仅从我的理解的角度写一些罢了,不是很严谨哟。^_^

啥也别说,先看一段算法程序吧。这段代码以前在blog中出现过(摘自MIT Press算法导论2nd),不过那时它是用来阐述'Pseudocode Conventions'的。
Insertion-Sort(A) △ A[1..n]
    for j <- 2 to length[A]
        do key <- A[j]
            △ Insert A[j] into the sorted sequence A[1..j-1].
            i <- j-1
            while i > 0 and A[i] > key
                do A[i+1] <- A[i]
                    i <- i-1
            A[i+1] <- key
假设我们目前没有学过什么算法复杂性分析之类的知识,如果让你去计算这个算法的运行时间的话,你会怎么做呢?最简单、最直观的方法就是把每条语句的执行时间累加在一起。对于上面这个简单的算法,我们'掰手指头'还是可以计算的。不过我们必须在计算前有个约定,什么约定呢,就是事先约定好一些'basic operation'的执行时间。我们定义一个'单位时间(UC, Unit Cost)'的概念,所有的语句的执行时间均为该'单位时间'的整数倍。那么这样我们可以约定并得出:
1、赋值操作、比较操作、算术运算、逻辑运算、访问(读写)单个常量或单个变量(包括一个数组的单个分量或一个记录的单个域)的时间为1 UC;
2、对于条件语句(if condition then …)和'switch condition case 1…n'语句来说,它们的执行时间为'计算condition值的时间' + '最耗时分支语句的执行时间',即T(condition) + max(Tcase1, Tcase2, … Tcasen);
3、对于for…loop语句,其执行时间显而易见为:'执行循环体的时间 x 循环次数',一般来说这个循环次数都是显式可知的;
4、对于do … while之类的循环语句,其执行时间类似于for … loop,为:'执行循环体的时间 x 循环次数',但其循环次数是处于隐含状态的;
5、对于goto语句,如果结构合理,无滥用goto的情况(如将控制权转移到goto前面的语句),其运行时间忽略不计;
6、对于函数或者是过程调用,它们需要的时间包括两部分,一部分用于实现控制转移,另一部分用于执行过程(或函数)本身,这时可以根据过程(或函数)调用的层次,由里向外运用规则(l)-(6)进行分析,一层一层地剥,直到计算出最外层的运行时间便是所求。

OK,知道了'时间约定',我们就来算算这个算法程序需要花费我们多长时间呢。
for j >> (n – 2 + 1) x 1 = n – 1;
key >> (n – 2 + 1) x 1 = n – 1;
i >> (n – 2 + 1) x 1 = n – 1;
while i > 0 and A[i] > key —>>> 由于while循环的'隐式执行次数',这里我们设该语句执行了Tj次,那么该条语句需要 (1 + 1 + 1) x Tj = 3 x Tj;
do A[i+1] >> (Tj – 1) x 1 = Tj – 1;
i >> (Tj – 1) x 1 = Tj – 1;
A[i+1] >> (n – 2 + 1) x 1 = n – 1;
我们来作和: Total_Running_Time = 4 x (n – 1) + Sum(3 x Tj) + 2 x Sum(Tj -1) = 4 x n – 4 + 3 x Sum(Tj) + 2 x Sum(Tj – 1); j belongs to [2,n]。这里唯一的未知量就是Tj,如何确定Tj呢?考虑两种极端的情况:
1、输入数字串是已经排好序的(already sorted) — Best Case
这里while i > 0 and A[i] > key语句只需执行一次,Tj = 1,这样我们可以得出:Total_Running_Time = 7 x (n – 1),即n的线性函数;

2、输入数字串是逆序的(reverse sorted) — Worst Case
此时A[i]要与A[1..j-1]的每一个元素比较,所以Tj = j – 1,这样我们可以得出:Total_Running_Time = 5/2 x (n^2 – n);

奇怪我们算出了两种不同的结果,到底采用那个呢?相信从直觉出发,大家也都会选择'Worst Case','Worst Case'给了我们一种保证(guarantee):针对某种规模的输入n,该算法能保证其时间复杂性不超过某个上界限(upper bound)。而'Best Case'大多是个'Cheating',毫无意义的(meaningless)。在大多数算法领域我们使用的也是'Worst Case'分析,还有一种分析方式叫'Average Case'分析,就拿上面的'INSERTION-SORT'而言,如何计算其'Average Case'的时间复杂性呢?'Average Case'一般依赖一个前提假设,而这个假设都符合一定的'Probability distribution',这里我们可以假定Tj = j/2,也就是说已经sorted的数字串中一半的值 > key,另一半 < key;这样计算出来的Total_Running_Time也是n^2一级的。

Ok,那么是不是针对每个算法都需要精确计算出其时间复杂性结果呢?我想不必要,在我们平时的工作中,多数时间是在选择算法,当然从事算法设计的专业人员除外,而选择算法的时候,我们大致只需要知道这个算法的一个时间上限即可,再根据特定的问题模型选择适当的算法。如何找到一个算法的时间复杂性上界是我们面临的问题。像INSERTINO-SORT这样的简单算法我们还可以处理,但随着问题规模的扩大,结构越来越复杂,算法分析的工作量之大、步骤之繁将令人难以承受,人们遂引入了'渐近性分析'方法,其主旨就是简化算法分析的工作量。看上面我们得到的INSERTION-SORT的'Worst Case'的结果:5/2 x (n^2 – n),这个结果中既包含n^2又包含n^1,对于这个简单的公式我们还是可以分析的,但是对于复杂的算法,可能存在这样的计算结果:n的诸多高次幂多项式,这样的多项式分析起来较为复杂,而渐近性恰是简化这样问题的好方法。

什么是渐近性?用数学语言表述就是:对于f(n),如果存在g(n),使得当n > 0, n -> ∞时有:(f(n) – g(n)) / f(n) -> 0,则g(n) 称为 f(n)的渐近表达式。用工程上的方法表述就是:g(n)是f(n)中略去低阶项(包括常数项)所留下的最高阶项,所以它无疑比f(n)来得简单。有了渐近表达式,寻找算法时间复杂性的界限就相对容易了。以后比较两个算法,就只需要比较两个算法的渐近表达式了,这样极大的简化了工作量。

我们定义了几种常用的渐近性符号用来对算法进行渐近性分析:
1、O符号
常用来分析算法复杂性上限(upper bound),其定义为:O(g(n)) = {对f(n),n为正整数,存在正整数常量C和N,使得0 <= f(n) = N},可以看出O(g(n))是一个集合,为了表示T(n)是该集合内的一个成员,我们将之表示为:T(n) = O(g(n))。

2、θ符号
常用来给出算法复杂性的上下限(lower bound and upper bound),其定义为:θ(g(n)) = {对f(n),n为正整数,存在正整数常量C1、C2和N,使得0 <= C1g(n) <= f(n) = N},可以看出O(g(n))也是一个集合,为了表示T(n)是该集合内的一个成员,我们将之表示为:T(n) = θ(g(n))。由于给出了上下限,所以θ符号集合为O符号集合的子集。

3、Ω符号
常用来分析算法复杂性的下限(lower bound),不常用。其定义为:Ω(g(n)) = {对f(n),n为正整数,存在正整数常量C和N,使得0 <= Cg(n) = N},可以看出O(g(n))是一个集合,为了表示T(n)是该集合内的一个成员,我们将之表示为:T(n) = Ω(g(n))。

有了这些符号我们再来看看如何理解带有渐近性符号的一些等式:
[例1] 渐近性符号仅仅用在等式右边
如:2n^2 + 6n + 1 = 2n^2 + θ(n),这里我们可以将该等式看成2n^2 + 6n + 1 = 2n^2 + a(n),这里a(n)是一个匿名函数,并且a(n)是θ(n)集合中的一个函数。

[例2] 渐近性符号出现在等式两边
如:2n^2 + θ(n) = θ(n^2),按照[例1]中匿名函数的方法,我们可以得到: 2n^2 + a1(n) = a2(n),其中a1(n)属于θ(n)集合,a2(n)属于θ(n^2)集合。这个等式需要这样理解"无论等式左边的匿名函数a1(n)取任何函数,等式右边的总存在一个匿名函数a2(n)使等式相等"。

以上是渐近性分析的一些基本知识,但是在实践中还是需要技巧的,实践证明在渐近性分析存在大量的递归函数,要想真正掌握复杂算法的渐近性分析,解决递归问题必不可少,不过这是以后的内容了。

我读书的TIMELINE

在’Blog on 27th Floor‘的blog上看到一篇名为’读书人的timeline‘的文章,文章中列出了各个年龄段读的书,我也觉得这是一个很有意思的话题,不妨也回顾一下自己这20几年曾经读过的书,模仿这种TimeLine格式列出来大家瞧瞧^_^。

我首先声明自己不是一个博览群书的人,但是我喜欢读书。这里的’书’指的是非专业类的书籍。小的时候是读书没有什么方向,长大了各种应试教育的功课压在身上,无暇读书;大学后则偏向专业书籍;工作后有了’博览群书的计划‘,但又迫于工作压力,进度并不明显,呵呵。

列出我的各个年龄段读过的书:
0 – 3岁 看图识字、听姥姥讲’一个屁咯嘣嘣,两个屁列个缝,三个屁连根拔’的故事(这应该是一个南方的故事,具体的情节我已经记不清了,但是这个故事的名字我却印象深刻)、听妈妈说汉字。

4 – 6岁 看小人书:三国演义、霍元甲…;看童话故事:’阿里巴巴与四十大盗’、’小红帽’、’海的女儿’、’胡桃夹子’;看好孩子画报:最喜欢小猪呼噜噜;看十万个为什么(虽然不是很懂);看动画书:黑猫警长、哪吒闹海、大闹天宫、超人…。

7 – 12岁(小学) 继续看’十万个为什么’(终于懂得一些道理)、看期刊:少年科学画报、新少年(在校生必须订阅的);看漫画:圣斗士星矢、机器猫; 看电视剧书:恐龙特急克塞号、变形金刚、百变雄狮。

13 – 15岁(初中) 学业繁重,以漫画:七龙珠为主要精神食粮,辅助幽游白书、乱马1/2。

16 – 18岁(高中) 开始接触大部头小说,包括中国古典名著、武侠小说和一些当代著名小说(似乎有点晚^_^)。当代小说:’平凡的世界’、’东方’;武侠小说:以金庸系列的为主:倚天屠龙记、天龙八部、神雕侠侣、笑傲江湖;古典名著:红楼梦(没怎么读懂)、西游记(没读全)、水浒传;名人出书:岁月随想(赵忠祥)。

19 – 22岁(大学) 看专业的书籍较多,不时地也看非专业的书籍以作消遣。看漫画:棋魂(大学里唯一看得上瘾的漫画);小说:海岩作品 ‘永不名目’、’玉观音’;科普读物:时间简史;网络小说:第一次亲密接触;外国小说:挪威的森林

22 – 至今(工作) 除了晚上和周末,就没什么自由支配时间,专业书籍占了大部分读书时间。其余时间看包括小说:达芬奇密码,哈利波特1-6,亮剑,深牢大狱(海岩),高效能人士的七种习惯,准备决定一切等。自己制定了今后的读书计划,只不过进度缓慢^_^。

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats