本书为**畅销书《大话设计模式》作者程杰潜心三年推出的扛鼎之作!以一个计算机教师教学为场景,讲解数据结构和相关算法的知识。通篇以一种趣味方式来叙述,大量引用了各种各样的生活知识来类比,并充分运用图形语言来体现抽象内容,对数据结构所涉及到的一些经典算法做到逐行分析、多算法比较。与市场上的同类数据结构图书相比,本书内容趣味易读,算法讲解细致深刻,是一本非常适合自学的读物。 本书以一个计算机教师教学为场景,讲解数据结构和相关算法的知识。通篇以一种趣味方式来叙述,大量引用了各种各样的生活知识来类比,并充分运用图形语言来体现抽象内容,对数据结构所涉及到的一些经典算法做到逐行分析、多算法比较。与市场上的同类数据结构图书相比,本书内容趣味易读,算法讲解细致深刻,是一本非常适合自学的读物。
本书主要内容包含:数据结构介绍、算法推导大O阶的方法;顺序结构与链式结构差异、栈与队列的应用;串的朴素模式匹配、KMP模式匹配算法;二叉树前中后序遍历、赫夫曼树及应用;图的深度、广度遍历;*小生成树两种算法、*短路径两种算法;拓扑排序与关键路径算法;折半查找、插值查找、斐波那契查找等静态查找;稠密索引、分块索引

第2章 算法
启
示 算 法:
算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。 2.1 开 场 白
各位同学大家好。
上次上完课后,有同学对我说,老师,我听了你的课,感觉数据结构没什么的,你也太夸大它的难度了。
是呀,我好像是强调了数据结构比较搞脑子,而上次课,其实还没拿出复杂的东西来说道。不是不想,是没必要,**次课就把你们糊弄晕,那以后还玩什么,逃课的不就更多了吗?你们看,今天来的人数和**次差不多,而且暂时还没有睡觉的。
今天我们介绍的内容在难度上就有所增加了,做好准备了吗?
2.2 数据结构与算法关系
我们这门课程叫数据结构,但很多时候我们会讲到算法,以及它们之间的关系。市场上也有不少书叫“数据结构与算法分析”这样的名字。
有人可能就要问了,那你到底是只讲数据结构呢,还是和算法一起讲?它们之间是什么关系呢?干吗要放在一起?
这问题怎么回答。打个比方吧,今天是你女友生日,你打算请女友去看爱情音乐剧,到了戏院,抬头一看——《梁山伯》18:00开演。嗯,怎么会是这样?一问才知,今天饰演祝英台的演员生病,所以梁山伯唱独角戏。真是搞笑了,这还有什么看头。于是你们打算去看爱情电影。到了电影院,一看海报——《罗密欧》,是不是名字写错了,问了才知,原来饰演朱丽叶的演员因为嫌弃演出费用太低,中途退演了。制片方考虑到已经开拍,于是就把电影名字定为《罗密欧》,主要讲男主角的心路旅程。哎,这电影还怎么看啊?
事实上,数据结构和算法也是类似的关系。只谈数据结构,当然是可以,我们可以在很短的时间就把几种重要的数据结构介绍完。听完后,很可能你没什么感觉,不知道这些数据结构有何用处。但如果我们再把相应的算法也拿来讲一讲,你就会发现,甚至开始感慨:哦,计算机界的前辈们,的确是一些很牛很牛的人,他们使得很多看似很难解决或者没法解决的问题,变得如此美妙和神奇。
也许从这以后,慢慢地你们中的一部分会开始把你们的崇拜对象,从帅哥美女、什么“哥”什么“姐”们,转移到这些大胡子或者秃顶的老头身上,那我就非常欣慰了。而且,这显然是一种成熟的表现,我期待你们中多一点这样的人,这样我们**的软件行业,也许就有得救了。
不过话说回来,现在好多大学里,通常都是把“算法”分出一门课单独讲的,也就是说,在《数据结构》课程中,就算谈到算法,也是为了帮助理解好数据结构,并不会详细谈及算法的方方面面。我们的课程也是按这样的原则来展开的。
2.3 两种算法的比较
大家都已经学过一门计算机语言,不管学的是哪一种,学得好不好,好歹是可以写点小程序了。现在我要求你写一个求1+2+3+……+100结果的程序,你应该怎么写呢?
大多数人会马上写出下面的C语言代码(或者其他语言的代码):
int i, sum = 0, n = 100;
for(i = 1; i < = n; i++)
{
sum = sum + i;
}
printf(" %d ", sum);
这是*简单的计算机程序之一,它就是一种算法,我不去解释这代码的含义了。问题在于,你的**直觉是这样写的,但这样是不是真的很好?是不是***?
此时,我不得不把伟大数学家高斯的童年故事拿来说一遍,也许你们都早已经听过,但不妨再感受一下,天才当年是如何展现天分和才华的。
据说18世纪生于德国小村庄的高斯,上小学的**,课堂很乱,就像我们现在下面那些窃窃私语或者拿着手机不停摆弄的同学一样,老师非常生气,后果自然也很严重。于是老师在放学时,就要求每个学生都计算1+2+…+100的结果,谁先算出来谁先回家。
天才当然不会被这样的问题难倒,高斯很快就得出了答案,是5050。老师非常惊讶,因为他自己想必也是通过1+2=3,3+3=6,6+4=10,……,4950+100=5050这样算出来的,也算了很久很久。说不定为了怕错,还算了两三遍。可眼前这个少年,为何可以这么快地得出结果?
高斯解释道:

用程序来实现如下:
int i, sum = 0,n = 100;
sum = (1 + n) * n / 2;
printf("%d", sum);
神童就是神童,他用的方法相当于另一种求等差数列的算法,不仅仅可以用于1加到100,就是加到一千、一万、一亿(需要更改整型变量类型为长整型,否则会溢出),也就是瞬间之事。但如果用刚才的程序,显然计算机要循环一千、一万、一亿次的加法运算。人脑比电脑算得快,似乎成为了现实。
2.4 算法定义
什么是算法呢?算法是描述解决问题的方法。算法(Algorithm)这个单词*早出现在波斯数学家阿勒?花刺子密在公元825年(相当于我们中国的唐朝时期)所写的《印度数字算术》中。如今普遍认可的对算法的定义是:
算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
刚才的例子我们也看到,对于给定的问题,是可以有多种算法来解决的。
那我就要问问你们,有没有通用的算法呀?这个问题其实很弱智,就像问有没有可以包治百病的药呀!
现实世界中的问题千奇百怪,算法当然也就千变万化,没有通用的算法可以解决所有的问题。甚至解决一个小问题,很**的算法却不一定适合它。
算法定义中,提到了指令,指令能被人或机器等计算装置执行。它可以是计算机指令,也可以是我们平时的语言文字。
为了解决某个或某类问题,需要把指令表示成一定的操作序列,操作序列包括一组操作,每一个操作都完成特定的功能,这就是算法了。
2.5 算法的特性
算法具有五个基本特性:输入、输出、有穷性、确定性和可行性。
2.5.1 输入输出
输入和输出特性比较容易理解,算法具有零个或多个输入。尽管对于绝大多数算法来说,输入参数都是必要的,但对于个别情况,如打印“hello world!”这样的代码,不需要任何输入参数,因此算法的输入可以是零个。算法至少有一个或多个输出,算法是一定需要输出的,不需要输出,你用这个算法干吗?输出的形式可以是打印输出,也可以是返回一个或多个值等。
2.5.2 有穷性
有穷性:指算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成。现实中经常会写出死循环的代码,这就是不满足有穷性。当然这里有穷的概念并不是纯数学意义的,而是在实际应用当中合理的、可以接受的“有边界”。你说你写一个算法,计算机需要算上个二十年,一定会结束,它在数学意义上是有穷了,可是媳妇都熬成婆了,算法的意义也不就大了。
2.5.3 确定性
确定性:算法的每一步骤都具有确定的含义,不会出现二义性。算法在一定条件下,只有一条执行路径,相同的输入只能有**的输出结果。算法的每个步骤被**定义而无歧义。
2.5.4 可行性
可行性:算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限次数完成。可行性意味着算法可以转换为程序上机运行,并得到正确的结果。尽管在目前计算机界也存在那种没有实现的极为复杂的算法,不是说理论上不能实现,而是因为过于复杂,我们当前的编程方法、工具和大脑限制了这个工作,不过这都是理论研究领域的问题,不属于我们现在要考虑的范围。
2.6 算法设计的要求
刚才我们谈到了,算法不是**的。也就是说,同一个问题,可以有多种解决问题的算法。这可能让那些常年只做有标准答案题目的同学失望了,他们多么希望存在标准答案,只有一个是正确的,把它背下来,需要的时候套用就可以了。不过话说回来,尽管算法不**,相对好的算法还是存在的。掌握好的算法,对我们解决问题很有帮助,否则前人的智慧我们不能利用,就都得自己从头研究了。那么什么才叫好的算法呢?
嗯,没错,有同学说,好的算法,起码要是正确的,连正确都谈不上,还谈什么别的要求?
2.6.1 正确性
正确性:算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
但是算法的“正确”通常在用法上有很大的差别,大体分为以下四个层次。
1.算法程序没有语法错误。
2.算法程序对于合法的输入数据能够产生满足要求的输出结果。
3.算法程序对于非法的输入数据能够得出满足规格说明的结果。
4.算法程序对于精心选择的,甚至刁难的测试数据都有满足要求的输出结果。
对于这四层含义,层次1要求*低,但是仅仅没有语法错误实在谈不上是好算法。这就如同仅仅解决温饱,不能算是生活幸福一样。而层次4是*困难的,我们几乎不可能逐一验证所有的输入都得到正确的结果。
因此算法的正确性在大部分情况下都不可能用程序来证明,而是用数学方法证明的。证明一个复杂算法在所有层次上都是正确的,代价非常昂贵。所以一般情况下,我们把层次3作为一个算法是否正确的标准。
好算法还有什么特征呢?
很好,我听到了说算法容易理解。没错,就是它。
2.6.2 可读性
可读性:算法设计的另一目的是为了便于阅读、理解和交流。
可读性高有助于人们理解算法,晦涩难懂的算法往往隐含错误,不易被发现,并且难于调试和修改。
我在很久以前曾经看到过一个网友写的代码,他号称这程序是“用史上*少代码实现俄罗斯方块”。因为我自己也写过类似的小游戏程序,所以想研究一下他是如何写的。由于他追求的是“*少代码”这样的**,使得他的代码真的不好理解。也许除了计算机和他自己,绝大多数人是看不懂他的代码的。
我们写代码的目的,一方面是为了让计算机执行,但还有一个重要的目的是为了便于他人阅读,让人理解和交流,自己将来也可能阅读,如果可读性不好,时间长了自己都不知道写了些什么。可读性是算法(也包括实现它的代码)好坏很重要的标志。
2.6.3 健壮性
一个好的算法还应该能对输入数据不合法的情况做合适的处理。比如输入的时间或者距离不应该是负数等。
健壮性:当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果。
2.6.4 时间效率高和存储量低
*后,好的算法还应该具备时间效率高和存储量低的特点。
时间效率指的是算法的执行时间,对于同一个问题,如果有多个算法能够解决,执行时间短的算法效率高,执行时间长的效率低。存储量需求指的是算法在执行过程中需要的*大存储空间,主要指算法程序运行时所占用的内存或外部硬盘存储空间。设计算法应该尽量满足时间效率高和存储量低的需求。在生活中,人们都希望花*少的钱,用*短的时间,办*大的事,算法也是一样的思想,*好用*少的存储空间,花*少的时间,办成同样的事就是好的算法。求100个人的高考成绩平均分,与求全省的所有考生的成绩平均分在占用时间和内存存储上是有非常大的差异的,我们自然是追求可以**率和低存储量的算法来解决问题。
综上,好的算法,应该具有正确性、可读性、健壮性、**率和低存储量的特征。
2.7 算法效率的度量方法
刚才我们提到设计算法要提**率。这里效率大都指算法的执行时间。那么我们如何度量一个算法的执行时间呢?
正所谓“是骡子是马,拉出来遛遛”。比较容易想到的方法就是,我们通过对算法的数据测试,利用计算机的计时功能,来计算不同算法的效率是高还是低。
2.7.1 事后统计方法
事后统计方法:这种方法主要是通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低。
但这种方法显然是有很大缺陷的:
? 必须依据算法事先编制好程序,这通常需要花费大量的时间和精力。如果编制出来发现它根本是很糟糕的算法,不是竹篮打水一场空吗?
? 时间的比较依赖计算机硬件和软件等环境因素,有时会掩盖算法本身的优劣。要知道,现在的一台四核处理器的计算机,跟当年286、386、486等老爷爷辈的机器相比,在处理算法的运算速度上,是不能相提并论的;而所用的操作系统、编译器、运行框架等软件的不同,也可以影响它们的结果;就算是同一台机器, CPU使用率和内存占用情况不一样,也会造成细微的差异。
? 算法的测试数据设计困难,并且程序的运行时间往往还与测试数据的规模有很大关系,效率高的算法在小的测试数据面前往往得不到体现。比如10个数字的排序,不管用什么算法,差异几乎是零。而如果有一百万个随机数字排序,那不同算法的差异就非常大了。那么我们为了比较算法,到底用多少数据来测试,这是很难判断的问题。
基于事后统计方法有这样那样的缺陷,我们考虑不予采纳。
2.7.2 事前分析估算方法
我们的计算机前辈们,为了对算法的评判更科学,研究出了一种叫做事前分析估算的方法。
事前分析估算方法:在计算机程序编制前,依据统计方法对算法进行估算。
经过分析,我们发现,一个用**程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素:
1.算法采用的策略、方法。
2.编译产生的代码质量。
3.问题的输入规模。
4.机器执行指令的速度。
第1条当然是算法好坏的根本,第2条要由软件来支持,第4条要看硬件性能。也就是说,抛开这些与计算机硬件、软件有关的因素,一个程序的运行时间,依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少。
我们来看看今天刚上课时举的例子,两种求和的算法:
**种算法:
int i, sum = 0,n = 100; /*执行1次*/
for(i = 1; i < = n; i++) /*执行了n+1次*/
{
sum = sum + i; /*执行n次*/
}
printf("%d", sum); /*执行1次*/
第二种算法:
int sum = 0,n = 100; /*执行一次*/
sum = (1 + n) * n/2; /*执行一次*/
printf("%d", sum); /*执行一次*/
显然,**种算法,执行了1+(n+1)+n+1次=2n+3次;而第二种算法,是1+1+1=3次。事实上两个算法的**条和*后一条语句是一样的,所以我们关注的代码其实是中间的那部分,我们把循环看作一个整体,忽略头尾循环判断的开销,那么这两个算法其实就是n次与1次的差距。算法好坏显而易见。 我们再来延伸一下上面这个例子:
int i, j, x = 0,sum = 0,n = 100; /*执行一次*/
for(i = 1; i < = n; i++)
{
for (j = 1; j < = n; j++)
{
x++; /*执行n×n次*/
sum = sum + x;
}
}
printf("%d", sum); /*执行一次*/
这个例子中,i从1到100,每次都要让j循环100次,而当中的x++和sum = sum + x;其实��是1+2+3+…+10000,也就是1002次,所以这个算法当中,循环部分的代码整体需要执行n2(忽略循环体头尾的开销)次。显然这个算法的执行次数对于同样的输入规模n = 100,要多于前面两种算法,这个算法的执行时间随着n的增加也将远远多于前面两个。
此时你会看到,测定运行时间*可靠的方法就是计算对运行时间有消耗的基本操作的执行次数。运行时间与这个计数成正比。
我们不关心编写程序所用的程序设计语言是什么,也不关心这些程序将跑在什么样的计算机中,我们只关心它所实现的算法。这样,不计那些循环索引的递增和循环终止条件、变量声明、打印结果等操作,*终,在分析程序的运行时间时,*重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。
可以从问题描述中得到启示,同样问题的输入规模是n,求和算法的**种,求1+2+…+n需要一段代码运行n次。那么这个问题的输入规模使得操作数量是f(n) = n,显然运行100次的同一段代码规模是运算10次的10倍。而第二种,无论n为多少,运行次数都为1,即f(n) = 1;第三种,运算100次是运算10次的100倍。因为它是f(n) = n2。
我们在分析一个算法的运行时间时,重要的是把基本操作的数量与输入规模关联起来,即基本操作的数量必须表示成输入规模的函数(如图2-7-1所示)。

图2-7-1
我们可以这样认为,随着n值的越来越大,它们在时间效率上的差异也就越来越大。好比你们当中有些人每天都在学习,我指有用的学习,而不是只为考试的死读书,每天都在进步,而另一些人,打打游戏,睡睡大觉。入校时大家都一样,但毕业时结果可能就大不一样,前者名企争抢着要,后者求职无门。
2.8 函数的渐近增长
我们现在来判断一下,两个算法A和B哪个更好。假设两个算法的输入规模都是n,算法A要做2n + 3次操作,你可以理解为先有一个n次的循环,执行完成后,再有一个n次循环,*后有三次赋值或运算,共2n + 3次操作。算法B要做3n + 1次操作。你觉得它们谁更快呢?
准确说来,答案是不一定的(如表2-8-1所示)。
表2-8-1
次数
算法A(2n + 3) 算法A’(2n) 算法B(3n + 1) 算法B’(3n)
n = 1 5 2 4 3
n = 2 7 4 7 6
n = 3 9 6 10 9
n = 10 23 20 31 30
n = 100 203 200 301 300
当n = 1时,算法A效率不如算法B(次数比算法B要多一次)。而当n = 2时,两者效率相同;当n > 2时,算法A就开始优于算法B了,随着n的增加,算法A要越来越好过算法B了(执行的次数比B要少)。于是我们可以得出结论,算法A总体上要好过算法B。
此时我们给出这样的定义,输入规模n在没有限制的情况下,只要超过一个数值N,这个函数就总是大于另一个函数,我们称函数是渐近增长的。
函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n > N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于g(n)。
从中我们发现,随着n的增大,后面的 +3还是 +1其实是不影响*终的算法变化的,例如算法A′与算法B′,所以,我们可以忽略这些加法常数。后面的例子,这样的常数被忽略的意义可能会更加明显。
我们来看第二个例子,算法C是4n + 8,算法D是2n2 + 1(如表2-8-2所示)。
表2-8-2 次数 算法C(4n+8) 算法C’(n) 算法D(2n2+1) 算法D’(n2)
n = 1 12 1 3 1
n = 2 16 2 9 4
n = 3 20 3 19 9
n = 10 48 10 201 100
n = 100 408 100 20 001 10 000
n = 1000 4 008 1 000 2 000 001 1 000 000
当n≤3的时候,算法C要差于算法D(因为算法C次数比较多),但当n > 3后,算法C的优势就越来越优于算法D了,到后来更是远远胜过。而当后面的常数去掉后,我们发现其实结果没有发生改变。甚至我们再观察发现,哪怕去掉与n相乘的常数,这样的结果也没发生改变,算法C′的次数随着n的增长,还是远小于算法D′。也就是说,与*高次项相乘的常数并不重要。
我们再来看第三个例子。算法E是2n2 + 3n + 1,算法F是2n3 + 3n + 1(如表2-8-3所示)。
表2-8-3
次数 算法E(2n2+3n+1) 算法E’(n2) 算法F(2n3+3n+1) 算法F’(n3)
n = 1 6 1 6 1
n = 2 15 4 23 8
n = 3 28 9 64 27
n = 10 231 100 2 031 1 000
n = 100 20 301 10 000 2 000 301 1 000 000
当n = 1的时候,算法E与算法F结果相同,但当n > 1后,算法E的优势就要开始优于算法F,随着n的增大,差异非常明显。通过观察发现,*高次项的指数大的,函数随着n的增长,结果也会变得增长特别快。
我们来看*后一个例子。算法G是2n2,算法H是3n + 1,算法I是2n2 + 3n + 1(如表2-8-4所示)。
表2-8-4 次数 算法G(2n2) 算法H(3n+1) 算法I(2n2+3n+1)
n = 1 2 4 6
n = 2 8 7 15
n = 5 50 16 66
n = 10 200 31 231
n = 100 20 000 301 20 301
n = 1,000 2 000 000 3 001 2 003 001
n = 10,000 200 000 000 30 001 200 030 001
n = 100,000 20 000 000 000 300 001 20 000 300 001
n = 1,000,000 2 000 000 000 000 3 000 001 200 000 3000 001
这组数据应该就看得很清楚。当n的值越来越大时,你会发现,3n+1已经没法和2n2的结果相比较,*终几乎可以忽略不计。也就是说,随着n值变得非常大以后,算法G其实已经很趋近于算法I。于是我们可以得到这样一个结论,判断一个算法的效率时,函数中的常数和其他次要项常常可以忽略,而更应该关注主项(*高阶项)的阶数。
判断一个算法好不好,我们只通过少量的数据是不能做出准确判断的。根据刚才的几个样例,我们发现,如果我们可以对比这几个算法的关键执行次数函数的渐近增长性,基本就可以分析出:某个算法,随着n的增大,它会越来越优于另一算法,或者越来越差于另一算法。这其实就是事前估算方法的理论依据,通过算法时间复杂度来估算算法时间效率。
2.9 算法时间复杂度
2.9.1 算法时间复杂度定义
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n) = O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。
这样用大写O( )来体现算法时间复杂度的记法,我们称之为大O记法。
一般情况下,随着n的增大,T(n)增长*慢的算法为*优算法。
显然,由此算法时间复杂度的定义可知,我们的三个求和算法的时间复杂度分别为O(n),O(1),O(n2)。我们分别给它们取了非官方的名称,O(1)叫常数阶、O(n)叫线性阶、O(n2)叫平方阶,当然,还有其他的一些阶,我们之后会介绍。
2.9.2 推导大O阶方法
那么如何分析一个算法的时间复杂度呢?即如何推导大O阶呢?我们给出了下面的推导方法,基本上,这也就是总结前面我们举的例子。
推导大O阶:
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中,只保留*高阶项。
3.如果*高阶项存在且不是1,则去除与这个项相乘的常数。
得到的结果就是大O阶。
哈,仿佛是得到了游戏攻略一样,我们好像已经得到了一个推导算法时间复杂度的**公式。可事实上,分析一个算法的时间复杂度,没有这么简单,我们还需要多看几个例子。
2.9.3 常数阶
首先顺序结构的时间复杂度。下面这个算法,也就是刚才的第二种算法(高斯算法),为什么时间复杂度不是O(3),而是O(1)。
int sum = 0,n = 100; /*执行一次*/
sum = (1+n)*n/2; /*执行一次*/
printf("%d", sum); /*执行一次*/
这个算法的运行次数函数是f(n)=3。根据我们推导大O阶的方法,**步就是把常数项3改为1。在保留*高阶项时发现,它根本没有*高阶项,所以这个算法的时间复杂度为O(1)。
另外,我们试想一下,如果这个算法当中的语句sum=(1+n)*n/2有10句,即:
int sum = 0, n = 100; /*执行1次*/
sum = (1+n)*n/2; /*执行第1次*/
sum = (1+n)*n/2; /*执行第2次*/
sum = (1+n)*n/2; /*执行第3次*/
sum = (1+n)*n/2; /*执行第4次*/
sum = (1+n)*n/2; /*执行第5次*/
sum = (1+n)*n/2; /*执行第6次*/
sum = (1+n)*n/2; /*执行第7次*/
sum = (1+n)*n/2; /*执行第8次*/
sum = (1+n)*n/2; /*执行第9次*/
sum = (1+n)*n/2; /*执行第10次*/
printf("%d",sum); /*执行1次*/
事实上无论n为多少,上面的两段代码就是3次和12次执行的差异。这种与问题的大小无关(n的多少),执行时间恒定的算法,我们称之为具有O(1)的时间复杂度,又叫常数阶。
注意:不管这个常数是多少,我们都记作O(1),而不能是O(3)、O(12)等其他任何数字,这是初学者常常犯的错误。
对于分支结构而言,无论是真,还是假,执行的次数都是恒定的,不会随着n的变大而发生变化,所以单纯的分支结构(不包含在循环结构中),其时间复杂度也是O(1)。
2.9.4 线性阶
线性阶的循环结构会复杂很多。要确定某个算法的阶次,我们常常需要确定某个特定语句或某个语句集运行的次数。因此,我们要分析算法的复杂度,关键就是要分析循环结构的运行情况。
下面这段代码,它的循环的时间复杂度为O(n),因为循环体中的代码须要执行n次。
int i;
for(i = 0; i < n; i++)
{
/*时间复杂度为O(1)的程序步骤序列*/
}
2.9.5 对数阶
下面的这段代码,时间复杂度又是多少呢?
int count = 1;
while (count < n)
{
count = count * 2;
/*时间复杂度为O(1)的程序步骤序列*/
}
由于每次count乘以2之后,就距离n更近了一分。也就是说,有多少个2相乘后大于n,则会退出循环。由2x=n得到x=log2n。所以这个循环的时间复杂度为O(logn)。
2.9.6 平方阶
下面例子是一个循环嵌套,它的内循环刚才我们已经分析过,时间复杂度为O(n)。
int i,j;
for(i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}
而对于外层的循环,不过是内部这个时间复杂度为O(n)的语句,再循环n次。所以这段代码的时间复杂度为O(n2)。
如果外循环的循环次数改为了m,时间复杂度就变为O(m×n)。
int i,j;
for(i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}
所以我们可以总结得出,循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。
那么下面这个循环嵌套,它的时间复杂度是多少呢?
int i,j;
for(i = 0; i < n; i++)
{
for (j = i; j < n; j++) /*注意int j = i而不是0*/
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}
由于当i = 0时,内循环执行了n次,当i = 1时,执行了n-1次,……当i = n-1时,内循环执行了1次。所以总的执行次数为
。
用我们推导大O阶的方法,**条,没有加法常数不予考虑;第二条,只保留*高阶项,因此保留n2/2;第三条,去除这个项相乘的常数,也就是去除1/2,*终这段代码的时间复杂度为O(n2)。
从这个例子,我们也可以得到一个经验,其实理解大O推导不算难,难的是对数列的一些相关运算,这更多的是考察你的数学知识和能力,所以想考研的朋友,要想在求算法时间复杂度这里不失分,可能需要强化你的数学,特别是数列方面的知识和解题能力。
我们继续看例子,对于方法调用的时间复杂度又如何分析。
int i,j;
for(i = 0; i < n; i++)
{
function(i);
}
上面这段代码调用一个函数function。
void function(int count)
{
print(count);
}
函数体是打印这个参数。其实这很好理解,function函数的时间复杂度是O(1)。所以整体的时间复杂度为O(n)。
假如function是下面这样的:
void function(int count)
{
int j;
for (j = count; j < n; j++)
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}
事实上,这和刚才举的例子是一样的,只不过把嵌套内循环放到了函数中,所以*终的时间复杂度为O(n2)。
下面这段相对复杂的语句:
n++; /*执行次数为1*/
function(n); /*执行次数为n*/
int i,j;
for(i = 0; i < n; i++) /*执行次数为n2*/
{
function (i);
}
for(i = 0; i < n; i++) /*执行次数为n(n + 1)/2*/
{
for (j = i;j < n; j++)
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}
它的执行次数 ,根据推导大O阶的方法,*终这段代码的时间复杂度也是O(n2)。
2.10 常见的时间复杂度
常见的时间复杂度如表2-10-1所示。
表2-10-1
执行次数函数 阶 非正式术语
12 O(1) 常数阶
2n+3 O(n) 线性阶
3n2+2n+1 O(n2) 平方阶
5log2n+20 O(logn) 对数阶
2n+3nlog2n+19 O(nlogn) nlog2n阶
6n3+2n2+3n+4 O(n3) 立方阶
2n O(2n) 指数阶
常用的时间复杂度所耗费的时间从小到大依次是:

我们前面已经谈到了O(1)常数阶、O(logn)对数阶、O(n)线性阶、O(n2)平方阶等,至于O(nlogn)我们将会在今后的课程中介绍,而像O(n3),过大的n都会使得结果变得不现实。同样指数阶O(2n)和阶乘阶O(n!)等除非是很小的n值,否则哪怕n只是100,都是噩梦般的运行时间。所以这种不切实际的算法时间复杂度,一般我们都不去讨论它。
2.11 *坏情况与平均情况
你早晨上班出门后突然想起来,手机忘记带了,这年头,钥匙、钱包、手机三大件,出门哪样也不能少呀。于是回家找。打开门一看,手机就在门口玄关的台子上,原来是出门穿鞋时忘记拿了。这当然是比较好,基本没花什么时间寻找。可如果不是放在那里,你就得进去到处找,找完客厅找卧室、找完卧室找厨房、找完厨房找卫生间,就是找不到,时间一分一秒的过去,你突然想起来,可以用家里座机打一下手机,听着手机铃声来找呀,真是笨。终于找到了,在床上枕头下面。你再去上班,迟到。见鬼,这一年的全勤奖,就因为找手机给黄了。
找东西有运气好的时候,也有怎么也找不到的情况。但在现实中,通常我们碰到的绝大多数既不是*好的也不是*坏的,所以算下来是平均情况居多。
算法的分析也是类似,我们查找一个有n个随机数字数组中的某个数字,*好的情况是**个数字就是,那么算法的时间复杂度为O(1),但也有可能这个数字就在*后一个位置上待着,那么算法的时间复杂度就是O(n),这是*坏的一种情况了。
*坏情况运行时间是一种保证,那就是运行时间将不会再坏了。在应用中,这是一种*重要的需求,通常,除非特别指定,我们提到的运行时间都是*坏情况的运行时间。
而平均运行时间也就是从概率的角度看,这个数字在每一个位置的可能性是相同的,所以平均的查找时间为n/2次后发现这个目标元素。
平均运行时间是所有情况中*有意义的,因为它是期望的运行时间。也就是说,我们运行一段程序代码时,是希望看到平均运行时间的。可现实中,平均运行时间很难通过分析得到,一般都是通��运行一定数量的实验数据后估算出来的。
对算法的分析,一种方法是计算所有情况的平均值,这种时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算*坏情况下的时间复杂度,这种方法称为*坏时间复杂度。一般在没有特殊说明的情况下,都是指*坏时间复杂度。
2.12 算法空间复杂度
我们在写代码时,完全可以用空间来换取时间,比如说,要判断某某年是不是闰年,你可能会花一点心思写了一个算法,而且由于是一个算法,也就意味着,每次给一个年份,都是要通过计算得到是否是闰年的结果。还有另一个办法就是,事先建立一个有2 050个元素的数组(年数略比现实多一点),然后把所有的年份按下标的数字对应,如果是闰年,此数组项的值就是1,如果不是值为0。这样,所谓的判断某一年是否是闰年,就变成了查找这个数组的某一项的值是多少的问题。此时,我们的运算是*小化了,但是硬盘上或者内存中需要存储这2050个0和1。
这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好,其实要看你用在什么地方。
算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)= O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。
一般情况下,一个程序在机器上执行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为O(1)。
通常,我们都使用“时间复杂度”来指运行时间的需求,使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时,通常都是指时间复杂度。显然我们这本书**要讲的还是算法的时间复杂度的问题。
2.13 总结回顾
不容易,终于又到了总结的时间。
我们这一章主要谈了算法的一些基本概念。谈到了数据结构与算法的关系是相互依赖不可分割的。
算法的定义:算法是解决特定问题求解步骤的描述,在计算机中为指令的有限序列,并且每条指令表示一个或多个操作。
算法的特性:有穷性、确定性、可行性、输入、输出。
算法设计的要求:正确性、可读性、健壮性、**率和低存储量需求。
算法特性与算法设计容易混,需要对比记忆。
算法的度量方法:事后统计方法(不科学、不准确)、事前分析估算方法。
在讲解如何用事前分析估算方法之前,我们先给出了函数渐近增长的定义。
函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n > N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于g(n)。于是我们可以得出一个结论,判断一个算法好不好,我们只通过少量的数据是不能做出准确判断的,如果我们可以对比算法的关键执行次数函数的渐近增长性,基本就可以分析出:某个算法,随着n的变大,它会越来越优于另一算法,或者越来越差于另一算法。
然后给出了算法时间复杂度的定义和推导大O阶的步骤。
推导大O阶:
? 用常数1取代运行时间中的所有加法常数。
? 在修改后的运行次数函数中,只保留*高阶项。
? 如果*高阶项存在且不是1,则去除与这个项相乘的常数。
得到的结果就是大O阶。
通过这个步骤,我们可以在得到算法的运行次数表达式后,很快得到它的时间复杂度,即大O阶。同时我也提醒了大家,其实推导大O阶很容易,但如何得到运行次数的表达式却是需要数学功底的。
接着我们给出了常见的时间复杂度所耗时间的大小排列:

*后,我们给出了关于算法*坏情况和平均情况的概念,以及空间复杂度的概念。
2.14 结 尾 语
很多学生,学了四年计算机专业,很多程序员,做了很长时间的编程工作,却始终都弄不明白算法的时间复杂度的估算,这是很可悲的一件事。因为弄不清楚,所以也就从不深究自己写的代码是否效率低下,是不是可以通过优化让计算机更加快速**。
他们通常的借口是,现在CPU越来越快,根本不用考虑算法的优劣,实现功能即可,用户感觉不到算法好坏造成的快慢。可事实真是这样吗?还是让我们用数据来说话吧。
假设CPU在短短几年间,速度提高了100倍,这其实已经很夸张了。而我们的某个算法本可以写出时间复杂度是O(n)的程序,却写出了O(n2)的程序,仅仅因为容易想到,也容易写。即在O(n2)的时间复杂度算法程序下,速度其实只提高了10倍,而对于O(n)时间复杂度的算法来说,那才是真的100倍。
也就是说,一台老式CPU的计算机运行O(n)的程序和一台速度提高100倍新式CPU运行O(n2)的程序。*终效率高的胜利方却是老式CPU的计算机,原因就在于算法的优劣直接决定了程序运行的效率。
也许你就可以深刻的感受到,愚公移山固然可敬,但发明炸药和推土机,可能更加实在和聪明(如图2-14-1所示)。

图2-14-1
希望大家在今后的学习中,好好利用算法分析的工具,改进自己的代码,让计算机轻松一点,这样你就更加胜人一筹。

第1章 数据结构绪论 1

1.1 开场白 2
如果你交给某人一个程序,你将折磨他一整天;如果你教某人如何编写程序,你将折磨他一辈子。
1.2 你数据结构怎么学的? 3
他完成开发并测试通过后,得意地提交了代码。项目经理看完代码后拍着桌子对他说:“你数据结构是怎么学的?”
1.3 数据结构起源 4
1.4 基本概念和术语 5
正所谓“巧妇难为无米之炊”,再强大的计算机,也要有“米”下锅才可以干活,否则就是一堆破铜烂铁。这个“米”就是数据。

1.4.1 数据 5
1.4.2 数据元素 5
1.4.3 数据项 6
1.4.4 数据对象 6
1.4.5 数据结构 6

1.5 逻辑结构与物理结构 7

1.5.1 逻辑结构 7
1.5.2 物理结构 9

1.6 抽象数据类型 11
大家都需要房子住,但显然没钱考虑大房子是没有意义的。于是商品房就出现了各种各样的户型,有几百平米的别墅,也有仅两平米的胶囊公寓……

1.6.1 数据类型 11
1.6.2 抽象数据类型 12

1.7 总结回顾 14 1.8 结尾语 15
*终的结果一定是,你对着别人很牛的说“数据结构——就那么回事。”
第2章 算法 17

2.1 开场白 18
2.2 数据结构与算法关系 18
计算机界的前辈们,是一帮很牛很牛的人,他们使得很多看似没法解决或者很难解决的问题,变得如此美妙和神奇。
2.3 两种算法的比较 19
高斯在上小学的**,老师要求每个学生都计算1+2+…+100的结果,谁先算出来谁先回家……
2.4 算法定义 20
现实世界中的算法千变万化,没有通用算法可以解决所有问题。甚至一个小问题,某个解决此类问题很**的算法却未必就适合它。
2.5 算法的特性 21

2.5.1 输入输出 21
2.5.2 有穷性 21
2.5.3 确定性 21
2.5.4 可行性 21

2.6 算法设计的要求 22
求100个人的高考成绩平均分与求全省所有考生的成绩平均分在占用时间和内存存储上有非常大的差异,我们自然追求**率和低存储的算法来解决问题。

2.6.1 正确性 22
2.6.2 可读性 23
2.6.3 健壮性 23
2.6.4 时间效率高和存储量低 23

2.7 算法效率的度量方法 24
随着n值越来越大,它们在时间效率上的差异也就越来越大。好比有些人每天都在学习,而另一些人,打打游戏、睡睡大觉,毕业后前者名企争着要,后者求职处处无门。

2.7.1 事后统计方法 24
2.7.2 事前分析估算方法 25

2.8 函数的渐近增长 27
2.9 算法时间复杂度 29
理解大O推导不算难,难的其实是对数列的一些相关运算,这考察的更多的是数学知识和能力。

2.9.1 算法时间复杂度定义 29
2.9.2 推导大O阶方法 30
2.9.3 常数阶 30
2.9.4 线性阶 31
2.9.5 对数阶 32
2.9.6 平方阶 32

2.10 常见的时间复杂度 35
有些时候,告诉你某些东西不可以去尝试,也是一种知识的传递。总不能非要去被毒蛇咬一口才知道蛇不可以去招惹吧。
2.11 *坏情况与平均情况 35
2.12 算法空间复杂度 36
事先建立一个有2050大的数组,然后把所有年份按下标数字对应,如果是闰年,此数组项的值就是1,如果不是就是0。这样,所谓的判断某一年是否是闰年就变成了查找这个数组的某一项的值是多少的问题。
2.13 总结回顾 37
2.14 结尾语 38
愚公移山固然可敬,但发明炸药和推土机,可能更加实在和聪明。
第3章 线性表 41

3.1 开场白 42
门外家长都挤在大门口与门里的小孩子的井然有序,形成了鲜明对比。哎,有时大人的所作所为,其实还不如孩子。
3.2 线性表的定义 42
3.3 线性表的抽象数据类型 45
有时我们想知道某个小朋友(比如麦兜)是否是班级的同学,老师会告诉我说,没有,麦兜是在春田花花幼儿园里。这种查找某个元素是否存在的操作很常用。
3.4 线性表的顺序存储结构 47
他每次一吃完早饭就冲着去了图书馆,挑一个好地儿,把他书包里的书,一本一本的按座位放好,长长一排,九个座硬是被他占了。

3.4.1 顺序存储定义 47
3.4.2 顺序存储方式 47
3.4.3 数据长度与线性表长度区别 48
3.4.4 地址计算方法 49

3.5 顺序存储结构的插入与删除 50
春运时去买火车票,大家都排队排着好好的,这时来了一个美女:“可否让我排在你前面?”这可不得了,后面的人像蠕虫一样,全部都得退后一步。

3.5.1 获得元素操作 50
3.5.2 插入操作 51
3.5.3 删除操作 52
3.5.4 线性表顺序存储结构的优缺点 54

3.6 线性表的链式存储结构 55
反正也是要让相邻元素间留有足够余地,那干脆所有元素都不要考虑相邻位置了,哪有空位就到哪里。而只是让每个元素知道它下一个元素的位置在哪里。

3.6.1 顺序存储结构不足的解决
办法 55
3.6.2 线性表链式存储结构定义 56
3.6.3 头指针与头结点的异同 58
3.6.4 线性表链式存储结构代码描述 58

3.7 单链表的读取 60
3.8 单链表的插入与删除 61
本来是爸爸左牵着妈妈的手、右牵着宝宝的手在马路边散步。突然迎面走来一美女,爸爸失神般地望着,此情景被妈妈逮个正着,于是扯开父子俩,拉起宝宝的左手就快步朝前走去。

3.8.1 单链表的插入 61
3.8.2 单链表的删除 64

3.9 单链表的整表创建 66
3.10 单链表的整表删除 69
3.11 单链表结构与顺序存储结构优缺点 70
3.12 静态链表 71
对于一些语言,如Basic、Fortran等早期的编程**语言,由于没有指针,这链表结构,按照前面我们的讲法,它就没法实现了。怎么办呢?

3.12.1 静态链表的插入操作 73
3.12.2 静态链表的删除操作 75
3.12.3 静态链表优缺点 77

3.13 循环链表 78
这个轮回的思想很有意思。它强调了不管你今生是穷是富,如果持续行善积德,下辈子就会好过,反之就会遭到报应。
3.14 双向链表 81
就像每个人的人生一样,欲收获就得付代价。双向链表既然是比单链表多了如可以反向遍历查找等的数据结构,那么也就需要付出一些小的代价。
3.15 总结回顾 84
3.16 结尾语 85
如果你觉得上学读书是受罪,假设你可以活到80岁,其实你*多也就吃了20年苦。用人生四分之一的时间来换取其余时间的幸福生活,这点苦不算啥。
第4章 栈与队列 87

**畅销书《大话设计模式》作者的新作!用户群更为广泛,写作风格一如既往,技术沉淀更加深厚,势必掀起全民数据结构的热潮!