时间空间复杂度

1、时间空间复杂度算法效率的度量 算法执行时间需要通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法：事后统计的方法 可以利用计算机的内部计时功能，先把程序编写好运行一下进行计时。不过这种方法有两个缺陷： 一是必须先编制好程序并运行； 二是所得出的时间统计量依赖于计算机的软硬件等环境因素，有时容易掩盖算法本身的优劣性。 事先分析估算的方法 A）依据的算法选用何种策略； B）问题的规模。例如求100以内还是10000以内的素数； C）书写程序的语言。对于同一个算法，实现语言的级别越高，执行效率就越低； D）编译程序产生的机器代码的质量； E）机器执行指

2、令的速度。 显然，同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，效率均不相同。 这表明使用绝对的时间单位衡量算法的效这表明使用绝对的时间单位衡量算法的效率是不合适的。率是不合适的。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数的函数。 一个算法是由控制结构控制结构（顺序、分支和循环）和原操作原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。 为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来

3、说是基本运算的原操作，以该基本操作重复执行的次数作为算法的时间量度。时间复杂度 时间复杂度： 一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 例如在如下所示的两个N*N矩阵相乘的算法中,“乘法”运算时“矩阵相乘问题”的基本操作。 for i:=1 to n do for j:=1 to n do begin ci,j:=0; for k:=1 to n do ci,j:=ci,j+ai,k*bk,j end; 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f (n)的极限值为不等于零的

4、常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n),称O(f(n) 为算法的渐进时间复杂度，简称时间复杂度。 整个算法的执行时间与该基本操作（乘法）重复执行的次数N成正比，记T(N)=O(N)。“O”的形式定义为：若f(n)是正整数n的一个函数，则xn=O(f(n)表示存在一个正的常数M，使得当n=n0时都满足|xn|=M|f(n)|空间复杂度 是程序运行所以需要的额外额外消耗存储空间,一般的递归算法就要有o(n)的空间复杂度了,简单说就是递归集算时通常是反复调用同一个方法，递归n次，就需要n个空间。（这个空间到底多大？我们姑且把它当作每次调用时分配的内存大小，到底多大，它

5、自己确定） 我们在判读算法的优劣时，往往是综合考虑时间复杂度和空间复杂度两个因素，一般是希望能够找到两个都省的方法，但事实上我们往往需要牺牲时间复杂度来成全空间，或牺牲空间来节省时间。因此我们需要根据题目要求，选择侧重节省的因素。 更多的时候由于空间的耗费我们一般可以容忍，所以我们会更关注时间复杂度对算法的影响。 例:给出一个还有n个数的有序序列，要求查给定的一个数x是否在序列中，若在则给出所在序列中所处的位置。输入：第一行输入两个数n和x 第二行为n个数输出：x在序列中所处的位置的序号样例：input： 6 61 12 35 58 60 61 100 output： 5顺序查找 从线性表的第

6、一个元素开始，依次将线性表中的元素被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。procedure search2(num:longint); var i,j:longint; begin for i:=1 to n do if ai=num then writeln(i);end; 二分查找法 若中间项的值等于 x ，则说明查到，查找结束。 若 x 小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找； 若 x 大于中间项的值，则在线性表的后半部分（即中间项以后的部分

7、）以相同的方法进行查找； 这个过程一直进行到查找成功或子表长度为 0 （说明线性表中没有这个元素）为止。 procedure search(num:longint); var top,end1,mid:longint; begin top:=0;end1:=n; if end-top1)and(atopnum) do begin mid:=(top+end1) div 2; if num=amid then top:=mid else end1:=mid; end; if atop=num then writeln(top); end; 显然，当有序线性表为顺序存储时才采用二分法查找，并且，二

8、分查找的效率要比顺序查找高得多。可以证明，对于长度为 n 的有序线性表，在最坏情况下，二分查找只需要比较 log 2 n 次，而顺序查找需要比较 n 次。 选择排序：Procedure selectsort (var r:arraytype); begin for i:=1 to n-1 do Begin k:=i; for j:=i+1 to n do begin if rjrk then k:=j end; if ki then begin temp:=ri; ri:=rk; rk:=temp; end; end; end; end; 冒泡排序：Procedure selectsort (

9、var a:arraytype);beginfor i:=1 to n-1 do for j:=1 to n-i do if ajaj+1 then begin temp:=aj; aj:=aj+1; aj+1:=temp; end;end; 插入排序： procedure inssort(var r:arraytype); begin r0:=-maxint; for i:=2 to n do begin j:=i-1; x:=ri; while x0 do begin write(i:6); bi:-bi-1; end; writeln;归并排序：procedure mergesort(s

10、,t:integer); var m,i,j,k:integer; begin if s=t then exit; m:=(s+t) div 2; mergesort(s,m); mergesort(m+1,t); i:=s; j:=m+1; k:=s; while(i=m) and (j=t) do begin if ai=aj then begin rk:=ai; inc(i); inc(k); end else begin rk:=ai; inc(j); inc(k); end; end; while i=m do begin rk:=ai; inc(i); inc(k); end; w

11、hile j=t do begin rk:=aj; inc(j); inc(k); end; for i:=s to do ai:=ri; end;快速排序：procedure qsort( l,r:longint);Var i,j,m,p,k:longint;begin m:=arandom(r-l)+l; i:=l;j:=r; repeat while aim do dec(j); if ij; if lj then qsort(l,j); if ir then qsort(i,r);end;排序方法平均时间最坏时间辅助存储选择排序O(n2)O(n2)O(1)冒泡排序O(n2)O(n2)O

12、(1)计数排序O(n)O(n)0归并排序O(nlog2n) O(nlog2n)O(n)插入排序O(n2)O(n2)O(1)快速排序O(nlog2n) O(nlog2n)O(log2n)几种排序算法的比较和选择 选取排序方法需要考虑的因素： (1) 待排序的元素数目n； (2) 元素本身信息量的大小； (3) 关键字的结构及其分布情况； (4) 语言工具的条件，辅助空间的大小等。 1) 若n较小(n = 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。 (2) 若文件的初始状态已按关键字基本有序，则

13、选用直接插入或冒泡排序为宜。 (3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法 军事机密军事机密 Time Limit: 10 secondMemory Limit: 2 MB 问题描述我军方截获的信息由n（n30000）个数字组成，因为是敌国的高端秘密，所以一时不能被破获。最原始的想法就是对这n个数进行从小到大排序，每个数都对应一个序号，然后对第i个是什么数感兴趣，现在要求编程完成。 Input 第一行是n，第二行是n个截获的数字，第三行是数字k，接着是k行要输出数的序号。 Output

14、k行序号所对应的数字。 输油管道问题输油管道问题 Time Limit: 10 secondMemory Limit: 2 MB问题描述某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置, 即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。编程任务：给定n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。Input由文件input.txt 提供输入

15、数据。文件的第1 行是油井数n，1n10000。接下来n 行是油井的位置，每行2个整数x和y，-10000 x，y10000。 Output程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是油井到主管道之间的输油管道最小长度总和堆 堆是一种特殊的二叉树 它满足V(左孩子)V(右孩子)或V(左孩子)V(根)ai do swap(i,i div 2); i:=i div 2; endw;end;堆选择与维出堆顶节点7127 37288338 68一、取出二、调整算法描述（堆排序） procedure sort; build; for i:

16、=1 to n do writeln(a1); delete(1); endp;类似于push,不过push是把小元素向上换，delete是把最小的删掉后，把最后一个元素放上来，这样就变成了把一个大元素向下放的过程，具体方法请自己思考。堆排序算法PROC shift (var r:listtype; k,m:integer); i:=k.j:=2*I; x:=rk.key;finish:=false t:=rk; while (j=m) and not finish do if (jrj+1.key) then j:=j+1; If x=rj.key then finish:=true Els

17、e ri:=rj; i:=j; j:=2*I ri:=tendPPROC heapsort(var r:listtype);For i:=n/2 downto 1 shift(r,I,n);For i:=n downto 2 do r1与与ri交换交换; shift(r,1,i-1) endP堆的应用 果子合并在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并

18、所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。 堆的应用 【输入文件】 输入文件fruit.in包括两行，第一行是一个整数n(1n=10000)，表示果子的种类数。第二行包含n个

19、整数，用空格分隔，第i个整数ai(1ai=20000)是第i种果子的数目。 【输出文件】 输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。 堆的应用 很明显，这道题是一道贪心的题目，可以证明，每次取最小的两堆合并会使得最后的体力值最小。 那么，这道题的问题就在于怎么找最小的两堆果子了。 注意到，每次合并完果子会删掉两堆，并添加一堆新的，如果采用线性表，时间复杂度将高达O（N2），对于N=20000是不够的。 所以，我们考虑用小根堆优化。堆的应用 算法： 建立空堆 每读入一个数插入堆中 每次取两个堆顶元素合并，并插入合并后的数，总共

20、合并n-1次。堆的应用用堆优化dijstra算法 例题：最小序列问题。例题：最小序列问题。 给定一个NN（N=100）的正整数矩阵。需要在矩阵中寻找一条从起始位置到终止位置的路径(可沿上下左右四个方向)，并且要求路径中经过的所有数字，其相邻数字之差的绝对值之和最小。例题分析 这道题的基本算法很简单，只要用Dijkstra算法求出从起始位置到终止位置的最短路径即可。但这当中存在一个很大的问题：NRoot; (b) q=p; p=p-Rchild; (c) q=p; p=p-Rchild; (d) r=NewNode2(x); q-Rchild=r2836332125pq(a)2836332125

21、q(b)p2836332125q(c)p283633432125qr(d)图83 二叉搜索树的构造过程 (a) 空树；(b) 插入28；(c) 插入21；(d) 插入25；(e) 插入36；(f) 插入33；(g) 插入43283633432125(g)2836332125(f)28362125(e)282125(d)2821(c)28(b)(a) 在二叉搜索树上删除一个结点也很方便。首先应搜索被删除的元素。搜索删除元素的方法与插入元素的做法类似，要求在从根结点往下搜索的过程中，记录下当前元素的双亲结点，并用指针q指示。如果不存在该元素，那么显示“No element with key”信息。

22、如果存在待删除的结点，设其由指针p指示，则删除结点*p的操作可分下面三种情况讨论。二叉搜索树的删除二叉搜索树的删除1）没有儿子，即为叶节点。直接把父节点的对应儿子指针设为NULL，删除儿子节点就OK了。2）只有一个儿子。那么把父节点的相应儿子指针指向儿子的独生子，删除儿子节点也OK了。二叉搜索树的删除二叉搜索树的删除二叉搜索树的删除二叉搜索树的删除3）有两个儿子。这是最麻烦的情况，因为删除节点之后，还要保证满足搜索二叉树的结构。其实也比较容易，我们可以选择左儿子中的最大元素或者右儿子中的最小元素放到待删除节点的位置，就可以保证结构的不变。当然，要记得调整子树，毕竟又出现了节点删除。这里选择左儿子的最大元素，将它放到待删节点的位置。左儿子的