第一章 算法分析基本概念

算法设计技巧与分析

信工学院软件与理论教研室

王培崇

2014年9月

纪律要求等情况说明：1、请勿随意缺课；2、交作业（会适当）；3、交试验报告(务必运行程序让我看结果，跟我说明程序的设计思想)4、实验纪律（点名出勤，缺课1/3则没有实验分数）5、最终分数=试卷（70%）+实验（30%）作业依据质量融入实验分数中；6、考试形式：按照往常年的情况就是7或8道分析设计题（10-15分/题）。

涉及编程、设计思想、求解步骤分析等。一般情况下是没有选择、填空、判断、简答等的题目。算法的直觉含义:一个由有限的指令集组成的过程.

Knuth教授的定义:一个算法就是一个有穷规则的集合,其中的规则确定了一个解决某一特定类型问题的运算序列.算法导论中的定义：定义良好的计算过程，它取一个或一组作为输入，并产生出一个或一组作为输出。

1.1引言

在计算机科学领域，算法设计与分析是十分重要的。D.E.Knuth说：“计算机科学就是算法的研究”。

算法的规则须满足特点:

(1)有穷性—执行有限条指令后一定要终止。(2)确定性(无二义)—算法的每一步操作都必须有确切定义，不得有任何歧义性。(3)可(能)行性—算法的每一步操作都必须是可行的，即每步操作均能在有限时间内完成。(4)输入—一个算法有n（n>=0)个初始数据的输入。(5)输出—一个算法有一个或多个与输入有某种关系的有效信息的输出。IT产业中算法的应用1、百度的深度学习研究院：招聘优秀的机器学习、深度学习、大数据处理、BI等算法人才；百度搜索引擎算法的研究；

2、Google为什么能够屹立业界：先进的搜索引擎处理算法、非开源的云计算架构；（注：hadoop是开源的）2、IT公司的竞争其实是科技含量的竞争，实质就是在算法、架构能否优先的竞争。3、优秀软件公司的组织结构：

a、CTO（首席架构师）

b、需求分析师：负责跟甲方沟通；

c、系统设计师+核心算法设计小组人员。

d、项目经理

e、编码人员（这个阶层人数最多）

f、测试小组；

g、质量管理人员。

微软高薪挖角：挖掉了borland

delphi的首席架构师等人，去做VS系列以及设计C#等。（PS:编译器中的优化算法等等各个公司的编译器均不相同。)搜索引擎中的各个算法处理方案也不尽相同。

DNA中基因对序列排队也会涉及复杂的算法。网络数据传输中的路由选择算法。（QQ、微信中的信息传输）

自动化软件测试中的路径测试用例自动生成技术。该问题也是一个复杂性相当强的问题，会产生组合爆炸。围棋软件、象棋软件等等（我们身边的：查询你自己的通话记录，有优秀算法的存在吗？数据库：优化、索引）科学研究中的算法1、图灵奖的获得者绝大部分是做算法的研究的；姚期智：受聘于清华大学计算机系，唯一的一个图灵奖华裔获得者。2、寻求计算方面的突破。可计算性理论与计算复杂性理论等等。

最简单的实例：围棋中的人工智能其实就是一个计算复杂性太大的问题，各种组合会产生组合爆炸的问题，在目前图灵机模型下没有办法进行突破。

排序算法的突破：寻求更快速、更稳定的排序算法。（基于比较的排序算法和非比较排序算法O(nlogn)、O(n)）

（1）国王奖励有功的大臣：棋盘放麦子的问题。说明一个问题：计算复杂性问题，没有知识是多么可怕啊。（2）网络安全：其实也是一个计算复杂性问题。没有绝对安全的网络，从理论上可以证明构建绝对安全的网络是一个完全NP问题，无法达到，只能寻求某种情况下的最优。（如果你不知道这些，会在上面浪费非常多的人力、无力，而没有任何效果，不能无限制满足甲方的不合理要求）3、美国计算机协会组织的ACM大赛。是目前为止，最受肯定的国际级别的比赛，主要专注的就是算法设计和编程。参赛者组成一个团队，以5个小时之内完成的算法和编程完成情况排名。（这个赛事备受各个大公司猎头的关注，亲们可以组队参加试试）4、跟大家毕业相关的算法介绍计算科学的算法实在是太多了，介绍几个如下：（1）排序算法：要考虑需要进行排序的数据的顺序程度、数据取值的可能限制、数据所处于介质如内存、磁盘、磁带等的情况。（2）倒排索引：搜索引擎中的算法；页面关联度分析算法等等；（3）海量数据中的查找算法；（4）图形、图像中的各种算法：高斯去噪；图像分割、图像内容提取、图像修复等等。（5）智能优化算法（最多）。遗传算法、蚁群算法、粒子群算法等等。用于解决那些无法找到确定性算法解决的问题，即NP问题。（这是我们毕业生做的最多的）（6）大数据中的数据挖掘、关联度分析等等算法。（7）软件保护中的加解密、水印算法等等。●20世纪30年代,人们的注意力是放在问题的可解与不可解的分类上,即是否存在有效过程来求解问题,为此产生了计算模型的概念.例如:递归函数、演算、POST机、

Turing机.●

令人惊奇的是“几乎所有”的问题都是不可解的。(请参考书上的说明，不做要求)●把问题的可判定性和可解性的研究领域称为可计算性理论或计算理论。

1.2历史背景●数字计算机出现后,对于可解问题研究的要求越来越多,由于有限的可用资源与开发复杂算法的要求,导致了在计算理论中出现了一个称为计算复杂性的新领域。●在此领域，人们研究可解类问题的效率。

注意：自本节起，在搜索与排序的问题以及类似问题中，均假定元素取自线序集合(如整数集)。

●考虑这样的问题：判定给定元素x是否在数组A[1…n]中。此问题可表述为：寻找索引j，1jn，如果x在A中，则有x=A[j]，否则j=0。1.3二分搜索

●解决该问题能够想到的最简单的方法：顺序扫描法（线性搜索）：算法思想如下：扫描A中所有项，将每一项与x比较，如果在比较j次后(1jn)搜索成功，即x=A[j]，则返回j的值，否则返回0，表示没有找到。算法1.1

LinearSearch伪码描述：Input:数组A[1…n]、欲搜索元素x。Output:若x=A[j]且1jn,输出j,否则输出0。

1.j12.while(jn)and(xA[j])//处理循环

3.jj+14.endwhile5.ifx=A[j]thenreturnj

else

return0.

上述搜索算法在一般情况下是没有问题的，但是在某些特殊情况下，如果仍然采用这种方法，是很愚蠢的处理方式。如果数据有序，我们就要考虑应用数据之间的关系，来迅速定位待查找数据所处位置。●一般地，令A[low…high]为升序数组，A[mid]为其中间元素。1、如果x=A[mid]，则j=mid,结束;2、如果x>A[mid]，则x必定在A[mid+1...high]中,此时丢弃A[low…mid],只需在A[mid+1…high]中搜索x;3、如果x<A[mid]，则x必定在A[low…mid-1]中,此时丢弃A[mid…high],只需在A[low…mid-1]中搜索x。算法1.2BinarySearch算法伪码：Input:n个元素的升序数组A[1…n]和元素x.Output:若x=A[j],1jn,输出j,否则输出0.1.low1;highn;j02.while(lowhigh)and(j=0)3.mid(low+high)/24.ifx=A[mid]thenjmid

//找到数据

5.else

ifxA[mid]thenhighmid-16.

elselowmid+17.endwhile8.returnj

显然，由数据的搜索过程分析，可以把二分搜索算法的执行描述为二元树的搜索过程，又称为：决策树。

如下图：其中黄色的节点是与待搜索元素ｘ进行比较的数字。

10、23、15、22

1.3.1二分搜索算法分析1023152212514879322735显然可以轻松得出结论：

数据X正好在数组的中间，算法1.2的比较次数是1，应该是最少的。

（注意：不是0）下面重点分析普通情况的算法复杂性，即什么情况下搜索次数最多。推理如下：

(3)第k次迭代循环时剩余元素数目是n/2k-1，现在的停止条件是搜索数组为1或找到该元素x。也就是说最大的循环次数就是上述公式的满足条件的k值。1=<n/2k-1<2则有k-1<=logn<kk=logn+1（1）第一次迭代A[mid+1..n]中剩余数据数目n/2或者是(n-1)/2，即n/2的下界：n/2；（包含了n是奇数或是偶数）(2)第二次迭代之后剩余的数据数目是n/2

/2=n/4；另外一种证明方法，决策树明显是一个二叉树：一棵二叉树的高度是logn比较次数就是logn+1。

定理1.1对于一个大小为n的排序数组，算法BINARYSEARCH执行比较的最大次数为logn+1。得到如下结论：●假设有数组A[1…m],p,q,r为其三个索引，并且满足：1pq<rm,两子数组A[p…q]和A[q+1…r]各自按升序排列。现重新安排A中元素的位置，使子数组A[p…r]也按升序排列。1.4合并两个已排序的表●算法工作思路：设置一个空数组，用于暂时存放数据：B[p…r]。

指针s、t初始时分别指向A[p]和A[q+1]，每次比较元素A[s]和A[t],将小的元素添加进数组B，即：1、如果A[s]A[t]，则A[s]添加进B,并且s加1；2、如果A[s]A[t]，则A[t]添加进B,并且t加1。3、当至少有一个数组为空时(即s=q+1或t=r+1时),只要将非空数组的剩余元素添加进B即可。4、最后,将数组B[p…r]复制回A[p…r]。算法1.3Merge伪代码Input:A[1…m]和其三个索引p,q,r,1pqrm两子数组A[p…q]和A[q+1…r]各自安升序排列.Output:合并A[p…q]和A[q+1…r]为数组A[p…r].1.Comment:B[p…r]是辅助数组.2.sp;tq+1;kp3.whilesqandtr

4.ifA[s]A[t]then5.B[k]A[s]6.ss+17.else8.B[k]A[t]

9.tt+110.endif11.kk+112.endwhile13.ifs=q+1then

//检查哪个数组还没有处理完

B[k…r]A[t…r]14.

elseB[k…r]A[s…q]

15.endif16.A[p…r]B[p…r]

//复制回去

下面分析排序数组A[p…r]中元素所需要的比较次数。●

必须强调的是：从现在起所说的算法执行所需要的比较次数是指元素比较，即输入数据中所含对象的比较。（非while循环）●设两子数组A[p…q]和A[q+1…r]的大小分别为n1和n2,n1n2,并且n1+n2=n

。1、如果A[p…q]中的所有元素都比A[q+1…r]中的元素小，则需要比较n1次；(循环选择A[p..q]中n1个元素依次与A[q+1..r]中的第一个元素进行比较，故是n1次。)否则，全部元素之间都需要比较一遍，比较次数最多为n1+n2-1=n-1。

（最后一个元素肯定不用比较了，故-1）观察结论1.1算法MERGE将两个大小分别为n1和n2的非空数组合并成一个大小为n1+n2=n的排序数组，当n1n2时,元素比较次数在n1到n-1之间。特别地，如果两子数组大小为n/2和n/2，需要比较的次数在n/2到n-1之间。●怎样确定元素的赋值次数呢？观察结论1.2

使用算法MERGE将两个数组合并成一个大小为n的有序数组，元素赋值的次数恰好是2n。（向数组B中赋值n次，将B向A中赋值n次）问题描述：

令A[1…n]为一个有n个元素的数组，一种对A中元素进行简单、直接排序的算法如下。算法思想：1、首先找到最小的元素，将其放入A[1]中；2、然后在剩下的n-1个元素中找到最小的元素，将其放入A[2]中；3、重复此过程直到找到第二大元素,并将其放入A[n-1]中。1.5选择排序算法1.4SelectionSortInput:n个元素的数组A[1…n]。

Output:按非降序排列的数组A[1…n]。

1.fori1ton-12.ki

//标记当前需要处理数据的位置

3.forji+1ton{查找第i小的元素}4.ifA[j]A[k]thenkj//保证k一直指向最小数

5.endfor6.ifkithen交换A[i]和A[k]

//赋值3次

7.endfor●算法(1.4SelectionSort)执行的元素比较次数为：比较次数：i=1时，比较次数是:n-1;i=2时，比较次数是：n-2;依次类推：i=n时，比较次数应该是n-n+1=1.

故总比较次数是：

(n-1)+(n-2)+…+2+1=n(n-1)/2

根据程序可以得到：程序由于采用的是标记交换位置下标的做法，故交换次数是0...n-1。

每次交换需要3次元素赋值，故元素赋值次数界于0与3(n-1)之间。//(A[k]<->A[i])观察结论1.3

执行算法SelectionSort所需的元素比较次数为n(n-1)/2，元素赋值次数界于0与3(n-1)之间。1.6插入排序●插入排序的基本思想：（将待排数据插入到已经有序的数组中的适当位置）1、从下标为1的子数组A[1]开始,其自然已排好序；2、将A[2]插入到A[1]的前面或者后面,如果A[2]<A[1]，插入到A[1]前面，否则插入到后面；3、继续这一过程，在第i次执行中,要将A[i]插入到已排好序的A[1…i-1]中适当位置；4、重复以上过程，直到所有元素都插入到数组中。算法1.5INSERTIONSORT

Input:n个元素的数组A[1…n]。Output:按非降序排列的数组A[1…n]。

1.fori2ton

//从第2个元素开始进行

2.xA[i]

//取出该数据,赋值操作

3.ji-1

//跟前面的数据开始比较

4.While(j>0)and(A[j]>x)//注意条件，比较的依据，A[j]>x就是比较。

5.A[j+1]A[j]

//将数据后移给x腾地，赋值

6.jj-1

//依次递减，直至最小处

7.endwhile8.A[j+1]x

//将X放在合适的位置上，赋值操作

9.endfor●算法INSERTIONSORT分析1、输入序列已按非降序排列时，元素比较次数是：n-1，（每一个元素A[i](2in)只和A[i-1]比较）；（A[j]>x进行比较）2、输入序列按照降序排列且所有元素均不相同时,元素的比较次数最大,最大次数为。

1+2+…+(i-1)+…+(n-1)=n(n-1)/2。（解释：i=2时，前面有1个元素，故是1；i=3时，前面有2个元素，故是2；i=j时，前面是j-1个元素，故是j-1；i=n时，前面是n-1个元素，故比较n-1次）观察结论1.1

执行算法InsertionSort的元素比较次数在n-1到n(n-1)/2之间。

元素赋值次数等于元素比较次数加上n-1（赋值次数的处理是错误的）。（分析错误：内循环比较1次就赋值1次，数据后移时候的赋值；外循环2到n的循环共n-2+1=n-1次赋值）

应该分开讨论赋值操作次数的问题，讨论如下：

1、当数组已经排好顺序时，内循环只比较，不进行任何数据的赋值，内循环赋值次数为0。外循环赋值次数2*(n-1)。2、当数组逆序时，每比较一次，内循环赋值一次，故内循环的赋值次数是：

1+2+…+n-1=n(n-1)/2总的比较次数是：n(n-1)/2+2*(n-1)3、杂乱无章时，内循环比较次数与赋值次数没有任何关系，无法确定内循环的赋值次数。假设为m，则0≤m≤n(n-1)/2，为m+2*(n-1).修改的插入排序算法1.fori2ton

//从第2个元素开始进行

2.xA[i]

//取出该数据,赋值操作

3.ji-1

//跟前面的数据开始比较

4.While(j>0)and(A[j]>x)//注意条件，比较的依据，A[j]>x就是比较。

5.A[j+1]A[j]

//将数据后移给x腾地，赋值

6.jj-1

//依次递减，直至最小处

7.endwhile8.if((j+1)<>i)9.A[j+1]x

//将X放在合适的位置上，赋值操作

10.endfor//减少外层循环的赋值次数，尤其对于已经排好序的情况1.7自底向上合并排序上述算法的比较次数均是n2级别。数据结构中“树”的的计算复杂性要明显较线性表低，所以我们考虑下面通过树的方式来构造排序。减少数据之间的比较次数。例如：排序如下数据序列：945217461234567892459146749251746945217461.7自底向上合并排序令A为待排序的n个元素的数组。算法基本思想：1、将数组分解为n个数组，每一个数组只有一个元素，两两组合进行排序；生成目标：大小为2的n/2个排序序列数组；

特例：n不是2的整数倍，则剩余一个元素,不做任何处理直接进入下一轮迭代。2、对由第一步生成的排序完成的数组，进行两两合并排序；目标：生成n/4个长度为4的排序序列；特例：a、剩余一组2元素排序数组或1个元素，则直接进入下一轮迭代；b、剩余三个元素（即一组2元素数组和一个一元素数组），则将它们进行排序合并生成一个3元素数组。3、继续这一过程…，在第j次迭代中,生成n/2j个大小为2j的排序序列.直至完成全部排序为止。剩余元素：如有k个剩余元素,1k2j-1，则将它们放在下一次合并中，如有k个剩余元素,2j-1<k<2j,则将它们合并,形成一个大小为k的排序序列。（注意：两两合并操作，所以第i次合并操作得到的数组长度应该是：2i-1,

如果剩余的元素数目正好小于或等于这个数，肯定是单独一组数据；

如果大于这个数据，肯定是存在两组单独的数据，所以肯定要进行合并操作。）算法1.6BOTTOMUPSORTInput:n个元素的数组A[1…n]。Output:按非降序排列的数组A[1…n]。1.t12.whiletn//注意循环次数，树的高度logn次3.st;t2s;i0;//因为每次合并都是2个数组所以t被乘以2，t//s是被合并数组的长度4.whilei+tn5.MERGE(A,i+1,i+s,i+t)//合并两个已排序表，红色标识合并数组的边界

6.ii+t；//t是原始数的2倍，两两合并，故通过此公式向后推动i值，确定前一个合并数组的后边界值

7.endwhile8.ifi+s<nthenMERGE(A,i+1,i+s,n)//用于处理多余的剩余元素合并，如果n是2的整数幂，则不被执行

9.endwhile●算法中的变量说明1、s存储被合并序列的大小,开始将s置初值1，每次执行外面的While循环时被乘以2。2、i+1,i+s,i+t

用来定义两个要排序的序列的边界。3、当n不是t的倍数时,执行第8步;在这种情况下,如果剩余元素数目(即n-i)大于s，就要在大小为s的序列和剩余元素之间在进行一次排序。

假设n为2的倍数，则不再需要执行第八步，即不会有多余的数据序列遗留。（1）算法迭代次数是树的高度number=logn;(2)第i次迭代过程中，应该具有n/2i-1个数据序列，每个数据序列长度是2i-1。（因为是按照每层都是2对数据序列合并）

（3）根据观察结论1.1可知，每次迭代过程中，每两对数据序列的比较次数应该是n1到n1+n2-1====》2i-1到2i-1。故第i次全部的元素的比较次数应该是(n/2j)*2i-1到(n/2j)*2i-1。设k=logn，则最小比较次数是最大比较次数是：nlogn-n+1●例1.3

自底向上合并排序举例（参见课本）●算法执行的元素比较次数分析●元素赋值的次数:由观察结论1.2可知：在每一次合并操作时,外部while循环每执行一次要进行2n次元素赋值，一共进行2nlogn次赋值。（logn是树的高度，迭代次数）（为什么是2n次：合并操作中：两个n的数组，先赋值到B，然后拷贝回A，故赋值次数是2n）。观察结论1.5

用算法BOTTOMUPSORT对n个元素的数组进行排序，当n为2的幂时，元素比较次数在(nlogn)/2到nlogn-n+1之间。执行该算法的元素赋值次数为2nlogn。1.8时间复杂性●

算法运行时间与空间的确定问题是算法分析的一个基本组成部分，称为计算复杂性问题。研究的主要目的是：

当给出合法输入时，为了得到输出，确定该算法运行所需的时间与空间。

例子：观察：自底向上排序算法最大比较次数：nlogn-n+1，选择排序比较次数是n(n-1)/2。假设每一次的元素比较时间是10e-6秒，我们设置一个128的数组进行排序，则两个算法分别是8e-4秒和0.008秒。换做另外一个数组1048576,则经过计算前者是20秒，后者则是6.4天。（所以我们在设计算法时更应该关注时间）

显而易见，说一个算法A对于输入x要用y秒运行是没有意义的。所以我们更应该关注的是给一个算法的最通常的衡量标准。1.在什么机器上和怎样执行的。2.用的是什么样的编程语言。3.编译器和程序员的能力如何。基于上述原因我们并不需要得出算法的确切时间1.8.1阶的增长影响程序的运行时间的要素：1.与其它算法比较运行时间，估计的时间是相对的而不是绝对;2.其次，一个算法要独立于机器，才能够衡量性能；3.再者，它还应该是技术独立的，也就是说，无论科技如何进步，我们对算法运行时间的测度始终成立；4.第四，最关心的是在大数据量输入时，算法的运行情况。●我们甚至也并不需要得出算法的近似时间，●事实上，要精确计算所有的运算次数，如果不是不可能的话，也是非常麻烦的。由于只对大数据量输入运行时间感兴趣，所以可利用讨论运行时间的增长率或增长的阶的方法来度量算法的效率。见图1.5

显然n3增长率更快，而logn的增长率要低很多。n3>n2>nlogn>n>lognf(n)=30n3+10;f(n)=100n3+50n+1显然随着n的增大，两个函数趋于相同.(渐进)所以：常数在函数中影响就较小。●

表1.1是时间复杂性分别为logn,n,nlogn,n2,n3,2n的算法的近似运行时间。

●一旦去除了表示算法运行时间的函数中低阶项和常数，我们就称是在度量算法的渐近运行时间(Asymptoticrunningtime)。在算法分析中,用“时间复杂性”来表示渐进时间。定义1.1

对任一计算步骤,如果它的代价总是以一个时间常量为上界,而不论输入数据或执行的算法,我们称该计算步骤为“元运算”。●常见的元运算举例：1.算术运算，包括加、减、乘和除；2.比较和逻辑运算；3.赋值运算，包括遍历表或树的指针赋值。●下面给出表示算法复杂性的几个符号。元运算

由于考虑的是渐进曲线，所以对于元运算的可以任意选择一个整数作为其系数。1.8.2符号●

INSERTIONSORT执行的比较次数（元运算）次数是(n2-n)/2,是n2阶的，故选择k为某个适当选择的正常数。则其运算次数比较最多是kn2即：算法的运行时间是(n2)。●可作如下解释:只要当排序元素的个数等于或超过某个阈值n0时，那么对于某个常量k>0，运行时间至多为kn2。（强调：数据量较大）

注意：数据量很大时，也不能说运行时间总是恰好为kn2。这样,符号提供了一个运行时间的上界,它一般不是算法的实际运行时间。给出符号的数学定义：定义1.2

令f(n)和g(n)是自然数集到非负实数集的两个函数，如果存在一个自然数n0和一个常数c>0,使得nn0时f(n)cg(n),则称f(n)为(g(n))。因此，如果limnf(n)/g(n)存在，那么

limnf(n)/g(n)=》f(n)=O(g(n))。●定义1.2说明f(n)不比g(n)的某个常数倍增长得更快;符号给出了算法运行时间的一个上界。●

eg.f(n)=5n3+7n2-2n+13,可以写成:

f(n)=5n3+(n2).这样表示对于低阶项不感兴趣。1.8.3符号●(读作“大omega”)符号在运行时间的一个常数因子内提供一个下界。●例如算法INSERTIONSORT的运行时间是(n)。自底向上算法运算时间是(nlogn)●可解释为：无论何时，当被排序的元素个数等于或超过某一个阈值n0时，那么对某个常数c>0，运行时间至少是n的c倍。自底向上的运行时间至少是nlogn的c倍。●符号也被广泛用于表示问题的下界，换句话说,它通常用来表示解决某一问题的算法的下界（最小运行时间）。符号的定义：定义1.3令f(n)和g(n)是自然数集到非负实数集的两个函数,如果存在一个自然数n0和一个常数c>0,使得nn0,f(n)cg(n)则称f(n)为(g(n))。因此，如果limnf(n)/g(n)存在，那么limnf(n)/g(n)0蕴含着f(n)=(g(n))。(也就是说：f(n)至少不比g(n)的某个倍数增长慢，起码是一样快的)●从定义1.2与1.3可以看出：

f(n)为(g(n))当且仅当g(n)为(f(n))。(即：f(n)是g(n)的上界，则g(n)就是f(n)的下界)

就像足球一样，中韩足球的成绩。冲出亚洲的过程中，我们现在找不到一个增长速率能够超越韩国足球的增长速率。（为什么不说巴西、阿根廷、荷兰、西班牙呢，因为那不是紧挨着的上界，注意区分）“你问我中国足球何时得第一，别吓着上帝。”--《青花瓷-国足》更深的理解：

如果一个算法的最小运算复杂度是(g(n))，则认为基于该算法的核心思路（比较、选择）无法设计出渐进复杂性小于g(n)的程序。1.8.4符号●

选择排序算法比较次数是n(n-1)/2（没有最少和最多），所以该算法执行元运算次数总是和n2成正比，由于每一个元运算需要一个常量时间，我们说算法SELECTIONSORT的运行时间(n2)(读做“thetan平方”)。

●

可做如下解释：

●这一符号是表示算法的精确阶的，它蕴含算法的运行时间有确切界限。

存在常数c1和c2，在n≥n0的任何大小的输入情况下：

c1n2<=runtime<=c2n2。表明，对于任意正整数n,算法SELECTIONSORT的运行时间为(n2)。符号的定义定义1.4：令f(n)和g(n)是自然数集到非负实数集的两个函数，如果存在一个自然数n0和两个正常数c1和c2,使得nn0时,c1g(n)f(n)c2g(n),则称f(n)为(g(n))的。因此如果limnf(n)/g(n)存在，那么limnf(n)/g(n)=c(其中c必须是一个大于0的常数)蕴含着f(n)=(g(n))。●与前两个不同，

符号给出了算法运行时间增长率的一个精确描述；可以认为，类似于,类似于，而类似于。●定义1.4的一个重要推论是:f(n)=(g(n))当且仅当f(n)=(g(n))并且f(n)=(g(n))。例如：虽然100nn，但100n=(n)(上界)；虽然n100n，但n=(100n)（下界）；虽然n100n，但是n=(100n)

（确切值）。eg1.f(n)=10n2+20n；n>=1时，f(n)<=30n2故算法的上界是O(n2);n>=1时，f(n)>=n2,故算法的下界是(n2)；n>=1时，n2<=f(n)<=30n2,故精确时间是（n2）。eg2.f(n)=ank+a'nk-1+......+a1n+a0

则考虑最高的项目阶的渐进变化，则应该有f(n)=(nk)；（最大运算时间）f(n)=(nk)(最小运算时间)f(n)=(nk)（精确运算时间）

eg3.f(n)=logn2求极限limf(n)/n=0，故f(n)=(n)，但不是（n）和（n）。eg4.f(n)=logn2

logn2=2logn,也就是说

前者和后者的变化速度是一样快的，所以有logn2=（logn）。对于固定常数k有lognk=（logn）.eg5.常数函数的特殊之处

(1)、（1）、（1）。1.9空间复杂性●算法使用的空间定义：算法工作所需要的空间。它不包括用来存储输入的空间（输入缓冲区）。●算法的占用内存空间与其运算是相互协调的，写入每一个内存单元都至少需要一定的时间。所以算法的空间复杂性不可能超过时间复杂性这样，有S(n)=(T(n))。（即：（T是该算法的上界））eg1.线性搜索、二分查找、选择排序、插入排序

(1);//只需要增加一个暂存单元eg2.合并两个数组算法中只增加了一个数组B（大小为n），则为(n)；eg3.自底向上的排序算法主要考虑的是中间进行合并时的数组大小，鉴于初始排序的数组大小是n，则B的最大长度应该是n。故是(n).eg4.组合n长度的字符，形成字符串，并输出。

因为不需要保存，设置一个最长的n数组即可，明显是(n)。

如果还要保存用于后期的处理，则成了n*n!=（(n+1)!）。●概念：

如果任何一个求解问题的算法必定是(f(n))，那么我们把在(f(n))时间内求解问题的任何算法都称为问题的最优算法。1.10最优算法例如：在12.3.2节将证明:对于大小为n的数组而言,任何用元素比较的方法进行数据排序的算法，其运行时间在最坏情况下必定是(nlogn)的。

不能期望任一个算法在最坏情况下的渐进运行时间少于nlogn。因此把在O(nlogn)时间内用元素比较法排序的任何算法称为基于比较的排序问题的最优算法。●顺便指出，在最优算法的定义中没有考虑空间复杂性，其原因有两点：1.首先是因为时间比空间宝贵的多，只要算法使用的空间在一个合理的范围内即不予考虑。2.其次，大多数已有的最优算法，在相互比较它们的空间复杂性时，往往是同处于(n)阶内的。1.11如何估计算法运行时间●背景：

1、对于元运算，全部进行相加可以得到精确解；（现实是不可取的）2、不存在一个固定的过程或计算方法得到算法的时间和空间；3、计算时间需要直觉和机智。

通过如下的一些技术可以实现估算运行时间：

(1)计算迭代次数；(2)计算元运算的频度；(3)使用递推技术●在相关的较多算法中（搜索、排序、矩阵处理）包含较多的是循环或类似结构，而运算时间与其密切相关。eg1.count1//假设n=2k1.count=0;//count用于计算迭代次数；2.whilen>=1//执行k+1次，k=logn；forj=1ton//执行n次，n/2，n/4，.......1次；count=count+1//endforn=n/2；

endwhilereturncount1.11.1计算迭代次数eg2.输入正整数n(记住结论，这个例子和1.15和2.16有关)count=0;//计算元运算的迭代次数fori=1tonm=

forj=1tom//循环执行依次为：n,n/2,n/3,.......n/n（均为下界）5.count=count+1//endforendforreturncount第5步故得出结论该步骤执行了（nlogn）次，整个算法运行时间是（nlogn）。eg3.如下程序//输入n=22k

count=0;fori=1tonj=2;whilej<=n//j=2，4,16,........,22k循环得到执行。j=j*j;count=count+1;endwhileendforreturncount//对于for循环讲，每一个while循环执行k+1次，即loglogn+1。则while的总执行次数是n(k+1)=n(loglogn+1)次。

运算时间是

(n(loglogn+1)）。2、计算基本运算的频度：

对于某些算法精确估算运行次数几乎是不可能的。单源最短路径、寻找最小生成树prim算法、深度优先搜索、计算凸包等（后续待讲）。可以挑选一个元运算，其运行频率在所有的运算中是最大的，即包含了其它的元运算。

定义1.6如果算法中一个元运算具有最高的频度，所有其他元运算的频度均在它的频度的常数倍内，则称这个元运算为基本运算。例如：两个有序数组（长度都是n）的合并运算。元素的赋值运算包含两部分，也是该算法中最有频度的运算（包含了比较运算）。2n次赋值运算。故时间复杂度是(n)。

3.在遍历一个链表时，可以选择设置或更新指针的运算为基本运算；2.在矩阵乘法算法中,可选数量乘法为基本运算；4.在图的遍历中，可以选访问节点的“动作”和对被访问节点的计数为基本运算。●然而，在选择基本运算时，有一点要注意。请看下面的例子：

●在问题中的几种常见基本运算：1.在搜索和排序算法中,若元素比较是元运算,则可选为基本运算；例1.自底向上排序法的分析：（1）基本运算来自merge算法，选择元素比较作为元运算的基本运算。（2）算法的比较总次数是(nlogn)/2和nlogn-n+1（n是2的倍数）。（3）此时比较次数的上界和下届均为nlogn次，则其精确运算次数也是nlogn。（4）当n不是2的倍数时，由于每一次只是增加了一个merge运算，而其也是nlogn级别的，故上述第三步的结论仍然成立。（５）依据上述可以得出结论运算时间与数据比较次数成正比，故运算时间是(nlogn)。例2、见如下程序修改的插入排序

fori=2tonx=a[i];

k=modbinarysearch(a[1..i-1]),x)

//修改的二分搜索，确定待插入位置forj=i-1downtok//找到待插入位置后，后移数据；a[j+1]=a[j]endfora[k]=x;endfor

分析：确定运算最多的元是：k=.......，被调用n-1次，根据二分搜索的比较次数计算最大是[log(i-1)]+1（定理1.1），故其总次数是n-1次的和=(nlogn)(很有诱惑力的结论)

但是实际上该算法应该是O(n2)。该算法和插入排序算法的赋值次数完全一样。

错误在于：将基于元素比较作为基本运算，而实际应该是元素的移动。

另外注意：在一些算法中，所有的元运算都不是基本运算。它可能是这样的情况：两种或者更多的运算结合在一起的频度与算法的运行时间成正比，在此情况下，用执行这些运算的总次数的函数来表示运行时间。eg3.实现数组中前k个整数相乘，后面的相加prod=1;sum=0;forj=1tokprod=prod*a[j];endforforj=k+1tonsum=sum+1；endfor

分析：没有基本的元运算；runtime正比于（time(加)+time(乘)）；即：存在n个元运算（加+乘）；故界是（n）；通过循环次数确定时间，循环总次数是k+(n-k)=n次。●一个计算运行时间的函数常常以递推关系的形式给出，即函数的定义之中包含了函数本身。例如在算法BINARYSEARCH中，令C(n)为大小为n的实例中执行的次数，则有递推关系：

当n=1时,C(n)=1;

当n2时,C(n)C(n/2)+1.于是，C(n)C(n/2)+1=C(n/2/2)+1+1=C(n/4)+1+1=…=logn+1因此，C(n)logn+1，故C(n)=(logn),即算法BINARYSEARCH的时间复杂性为(logn)。1.11.3使用递推关系1.12最坏情况和最好情况的分析

1、考虑两个nn的整数矩阵A和B的相加问题。

运行时间与输入值无关只与维度有关2、SELECTIONSORT算法（选择排序）

算法的运行时间与输入的值无关。3、插入排序INSERTIONSORT，自底向上排序等等。运行时间在很大程度上与输入值有关。这表明算法不仅是输入n的函数，也是输入元素初始顺序的函数，算法运行时间不仅依赖于输入数据的个数，还依赖于它的形式，

我们一般情况下很难找到一个与输入大小和形式都相关的描述算法时间复杂性的函数，后一因素往往只能被忽略。见课本图1.6所示，对于插入排序，不同的排列次序，其时间复杂度是不同的。如果已经按升序排好：是n;随机安排：n2/4；降序排列：n2/2例如:

插入排序：对于一个数据输入序列n，最坏复杂度的上界与下界均是n2阶的，所以使用（n2）表示。表达算法在最坏情况下的确切性能。1、最坏情况下是（f(n)），蕴含了最坏情况下(f(n)).2、最坏情况下是O(f(n))，则无法推知下界是否是(f(n))。

1.12.1最坏情况分析

3、最坏情况下说以确切的(f(n))，要比使用上界O(f(n))强，更易理解；例子：线性搜索linesearch一般情况下是O(n)(上界)和（1）