算法设计与分析一纸开卷资料.docx

1、算法设计与分析一纸开卷资料一、算法时间复杂性问题1. 试证明下面的定理：(1)如果f(n)=O(s(n)并且g(n)=O(r(n),则f(n)+g(n)=O(s(n)+r(n);(2)如果f(n)=O(s(n)并且g(n)=O(r(n),则f(n)*g(n)=O(s(n)*r(n)根据符号O的定义，存在正常数C1，C2和自然数N1,N2，使得对所有的n= N1，f（n）= N2,g(n) =C2r(n)所以 f（n）+ g(n) = C1s(n)+ C2r(n)，f（n）*g(n)= C1C2s(n)r(n)；令 C3=max（C1,C2），C4=C1*C2；则：f（n）+ g(n) = C3

2、s(n)+ r(n)=O(s(n)+ r(n) f（n）*g(n) = C4*s(n)*r(n)=O(s(n)* r(n)2. 假设某算法在输入规模为n时的计算时间为：T（n）=3*2n ，在A型计算机上实现并完成该算法的时间为t秒，现有更先进的B型计算机，其运算速度为A型计算机的64倍。试求出若在先进的B型机上运行同一算法在则T秒内能求解输入规模为多大的问题？某台t秒内完成的基本运算的次数=3*2n新机器t秒内完成的基本运算的次数=64*3*2n=26*3*2n=3*2(n+6)设N为B型机上t秒钟能求解的问题的规模所以T=T(N)=3*2N=3*2(n+6) 则：N=n+6 3. 试说明为

3、什么“在现代计算机上运行指数（如2n）时间算法是不可能的，要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法计算复杂度的数量级，而不是提高计算机的速度”。(1)(log2n)(n)(nlog2n)(n2)(nn)一个计算时间为(1)的算法，它的基本运算执行的次数是固定的，因此，总的时间由一个常数(即，零次多项式)来限界，而一个时间为(n2)的算法则由一个二次多项式来限界。以下六种计算时间的多项式时间算法是最为常见的，其关系为(2n)(n!)(nn)指数时间算法一般有(2n)、(n!)和(nn)等。其关系为：其中，最常见的是时间为(2n)的算法。当n取得很大时，指数时间算法和多项式时间

4、算法在所需时间上非常悬殊因为根本就找不到一个这样的m，使得2n囿界于nm。换言之，对于任意的m0，总可以找到n0，当nn0时，有2nnm。因此，只要有人能将现有指数时间算法中的任何一个算法简化为多项式时间算法，那就取得了一个伟大的成就。(log2n)、(n)和(nlog2n)比另外三种时间函数的增长率慢得多。 由这些结果可看出，当数据集的规模(即n的取值)很大时，要在现代计算机上运行具有比(nlog2n)复杂度还高的算法往往是很困难的。尤其是指数时间算法，它只有在n值取得非常小时才实用。尽管通过提高计算机的速度比之前快1000倍，甚至10000倍，但当指数规模的n足够大时，n每增加1，1000

5、倍的提速即可瞬间化为乌有，所以要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度的数量级，而不是提高计算机的速度。二、简答1.对计算复杂性的研究能够使人们弄清所求解问题的固有难度，并得出评价某类算法优劣的准则，用以指导设计出更高效的算法。试用简短的语言说明“建立一个问题复杂性的下界要比确定它的上界困难得多！”其复杂性上界是已知求解该问题的最快算法的费用，而复杂性下界只能通过理论证明来建立。寻求某个问题的计算复杂性上界，只要研究一个算法的复杂性即可。但是要寻求同一问题的计算复杂性下界，则必须考察所有的解决该问题的算法，证明一个问题的复杂性下界就需要证明不存在任何复杂性低于下

6、界的算法。显然，建立下界要比确定上界困难得多。2.满足何种性质的问题被称为NP完全问题？请简述研究NP完全问题的意义；（1）NP即是多项式复杂程度的非确定性问题。 而如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题。如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内解决。（2）NP完全是指这样一类NP问题,所有的NP问题都可以用多项式时间划归到他们中的一个.所以显然NP完全的问题具有如下性质:它可以在多项式时间内求解，当且仅当所有的其他的NP完全问题也可以在多项式时间内求解。这样一来,只要我们找到一个NP

7、C问题的多项式解,所有的NP问题都可以多项式时间内划归成这个NPC问题,再用多项式时间解决,这样NP就等于P了.NP完全性理论的重要性:知道一个问题是NP完全的就给我们提供了有价值的信息，告诉我们采用什么样的途径可以是最富有成效的。一定不要去优先寻找有效的、精确的算法。现在比较适当的途径是集中精力致力于其他较低目标的方法。例如，你可以寻找解决这个问题的各种特殊情况的有效算法。寻找在大多数情况下看来能快速运算的算法，虽然不能保证它在任何情况下都能快速地运算。或者你甚至可以放松问题的某些方面，寻找一个只能给出满足大部分要求的快速算法。简言之，NP完全性理论的初步应用是帮助算法设计人员找到最有可能得

8、到有用的算法的努力方向3. “当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质”。问题的最优子结构性质是该问题可用动态规划算法求解的基本要素，试简要阐述“论证某一问题的最优子结构性质”时的一般方法；矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的

9、前提。同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）例如：假设（y1,y2,yn）是0-1背包问题的一个最优解，而（y2,yn）是相应子问题的一个最优解，有 假设（y2,yn）不是一个最优解，而（z2,zn）是最优解，由此可知，这说明（y1,z1,z2,zn）是问题的整体最优解，与（y1,y2,yn）是最优解矛盾，所以证明了最优子结构性质！三、算法设计与分析问题1. 最大值和最小值问题的最优算法（18）给定n个实数存放于一维数组A中，试设计一个算法在最坏情况下用3n/2-2次的比较找出A中的最大值和最小值（为简化，可假设n为偶数）。2. 社会

10、名流问题在 n个人中，一个被所有人知道但却不知道别人的人，被定义为社会名流。现在的问题是如果存在，试找出该社会名流。你可以使用的唯一方式是询问：“对不起，请问你知道那个人吗？”（假定所有回答都正确，甚至这位社会名流也将回答。）我们的最终目标是将询问的数目最小化。给定一个nn邻接矩阵，确定是否存在一个i，其满足在第i列所有项（除了第ii项）都为1，并且第i行所有项（除了第ii项）都为0。大致的算法思路：随便取一个非对角线元素比如Arrayij，如果Arrayij=0成立，则j不是社会名流，于是删去第j行和第j列。同样，如果Arrayij=1成立，则删去第i行和第i列；总之，无论对应项取何值，都可

11、以删去一行和一列，因此整个操作只耗费O(n)的时间。重复此操作直至剩下最后一个元素。最后，检验该元素是否为社会名流即可。如果该元素不是，则该群人中不存在社会名流。3.数列极差问题 在黑板上写了N个正数组成的一个数列，进行如下的操作：每一次任选其中的两个数设为a和b，将其擦去，然后在数列中加入一个新的数a*b+1，如此下去直至黑板上只剩下一个数为止。在所有按这种操作方式最后得到的数中，最大的数记为Max，最小的数记为Min，则该数列的极差定义为M=Max-Min。贪心算法最重要的两个性质是：贪心选择性质和最优子结构性质。贪心选择性质是所求问题的整体最优解可以通过一系列局部最优的选择，也就是贪心选

12、择来达到。而最优子结构性质是指一个问题的最优解包含其子问题的最优解。 问题的关键就是MAX MIN值的求解问题，所以首先看下怎么样来求MAX MIN值。设有三个数x y z,且xynum2num3。所以我们可以得出结论：优先选择数列中最小的2个数进行（a*b+1）运算得到的值大，优先选择数列中最大的2个数进行（a*b+1）运算得到的值小。我们可以把整体的MAX，MIN值通过一系列局部求MAX,MIN值来求我们想要的结果。 我们再看下用贪心策略求解的合理性：假设经（N3）次运算后得到3个数：x y max（maxxy），其中max是（N2）个数经（N3）次运算后所得的最大值，此时最大值m （x*

13、y1）max1。若经（N2）次变换后所得的3个数为：x y z（zxy）且z不为（N2）次变换后的最大值，即zmax则所求得的最大值为： m（x*y+1）*z+1， 此时mm（1+x*y）（maxz）0 所以此时不为最优解。 所以若使第k（1kN1）次变换后所得值最大，必使（k1）次变换后所得值最大（符合贪心策略的最优子结构性质），在进行第k次变换时，只需取在进行（k1）次变换后所得数列中的两最小数x，y进行运算，再把结果插入到数列即可。所以综上所述：该算法可以简单的描述为：MAX：不断地取当前黑板上的两个最小的数进行运算并且放回，会使最后的结果最大。MIN：不断地取当前黑板上的两个最大的数进

14、行运算并且放回，会使最后的结果最小。数列极差就是：MAX-MIN！算法设计： 先将数列an按从小到大进行排列(快速排序) 进行最大值的计算：选出an中最小的两个数进行（a*b+1）运算，在把运算结果按从小到大插入到数列中。一直这样运算，最后就可以得出MAX值。 进行最小值的计算：选出an中最大的两个数进行（a*b+1）运算，在把运算结果按从小到大插入到数列中。一直这样运算，最后就可以得出MIN值。 最后该数列的极差M =MAX-MIN4. 试说明如何修改快速排序算法，使它在最坏情况下的计算时间为O(nlgn)。可以通过减少递归栈的使用进行优化，快速排序的实现需要消耗递归栈的空间，而大多数情况下

15、都会通过使用系统递归栈来完成递归求解。对系统栈的频繁存取会影响到排序的效率。在数据量较大时，快速排序的复杂度为O(nlgn)。当数据集较小时，快排的复杂度有向O(n2)发展的趋势，此时不必继续递归调用快速排序算法，使用插入排序代替快速排序。STL中sort就是用的快排+插入排序的，使得最坏情况下的时间复杂度也是O(nlgn)这一改进被证明比持续使用快速排序算法要有效的多。使用一个快速排序的迭代模型可以使原递归算法所需的栈空间总量减至O（logn）。试设计这一迭代模型（算法）。struct nodeint low,high;st10000;void quicksort2(int data,int

16、 s,int t)int top=-1,low,high; top+; sttop.low=s; sttop.high=t; while(top-1) low=sttop.low; high=sttop.high;top-; int w; if(loww(v),则将v从T删除之后，T变为两个连同的分支，此时，一定有T的边v1连同这两个分支，否则T将是不连通的。从而将v1加入到T中构成一新的生成树T=T-v+v1。且有w(v1)w(v)w(v),从而w(T”)=w(T-v+v1)w(T)。这与T为最小生成树矛盾。证毕。据此利用prim算法或者Kruskal算法算得G的最小生成树即可Prim算法

17、O(n2)首先置 S=1，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。在上述Prim算法中，还应当考虑如何有效地找出满足条件iS, jV-S，且权cij最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。Kr

18、uskal算法 O(eloge)首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。6. 试设计在O(n)时间内求得数组A1.n的中位数的算法。将n个输入元素划分成n/5(上取整)个组，每组5个元素，只可能有一个组不是

19、5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5(上取整) 个。找出这n/5(上取整)个元素的中位数。如果n/5(上取整)是偶数，就找它的2个中位数中较大的一个。7. 两个数组找第k小元素事件复杂度O(log(k) )在网上看的，和同学商讨过，可行，认为此方法比上个log（m）+log（n）的方法要好 第一个数组m个元素 第二个数组n个元素分别从两个数组找第k/2个数，ak/2,bk/2;假设ak/2bk/2; 则ak/2 之前的以及ak/2都可以删去，并且k=k - 删去的元素下面分析为什么可以删去：因为ak/2bk/2,所以ak/2前至少有k/2-1个元素，

20、至多有k/2-1 + k/2-1 =k-2 个元素，因为ak/2 and bk/2 之后的都不可能在ak/2 之前，所以ak/2排在最后时也排在第k-1个位置，都小于第k个元素，所以可删去。其他情况同理；当m或n小于k/2时，假设mX3，则A先猜出，否则就是C先猜出），这样就又安装上面的思路求解。这显然就是一个递归求解的过程。设函数Times(i,j,t1,t2,t3)表示编号为t1的人头上的数为i，编号为t2的人的数为j，编号为t3的人的数为i+j（即由t3最先猜出自己的数）时，教授需要提问的次数；P（t1,t2）表示教授按照1-2-3的顺序，从t1问到t2，最少需要提问的次数，则根据上面的

21、分析，有如下关系： t3, i=jtimes(i,j,t1,t2,t3)=jtimes(i,j-i,t1,t3,t2)+P(t2,t3), it1时，P(t1,t2)=t2-t1,否则，P(t1,t2)=t2+3-t1寻找丢失的数！类C语言：用一个二维数组保存数组中的数的二进制位，然后从右往左按列扫描，然后确定之后删除被排除的行和，然后扫描第二次。特殊的整理：桶排序：桶排序工作的原理是：将阵列分到有限数量的桶子里。每个桶子再个别排序。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（n）。要对大小为1.1000范围内的n个整数A1.n排序，可以把桶设为大小为10的范围，具体而言，设

22、集合B1存储1.10的整数，集合B2存储(10.20的整数，集合Bi存储(i-1)*10, i*10的整数，i = 1,2,.100。总共有100个桶。然后对A1.n从头到尾扫描一遍，把每个Ai放入对应的桶Bj中。 然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。 假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果对每个桶中的数字采用快速排序，那么整个算法的复杂度是O(n+m*n/m*log(n/m)=O(n+nl

23、ogn-nlogm) 从上式看出，当m接近n的时候，桶排序复杂度接近O(n)。简答题：贪心和动态规划的区别！主要理解贪心的思想 局部！所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。雏形整理第一章和第二章：算法特性：有穷，可行，确定，输入，输出 四元组（Q，I，f）时间复杂性的定义掌握，理解上界，下界和精确界的证明过程，已经背下来了，分为多项式时间算法和指数时间算法； O(1) O(log n) O(n) O(n log n ) O(n2) O(2n) O(n!) O(nn) 买鸡问题：void chicken_problem(int n,int &k