算法期末一纸开卷

1.试证明下面的定理：（11分）(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的定义，存在正常数Ci和自然数Ni，使得对所有的n=N有i=1.2，f（n）=C1s(n)，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=C1C2；～则：f（n）+g(n)=C3[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秒内能求解输入规模为多大的问题？（5分）某台t秒内完成的基本运算的次数=3*2^n～新机器t秒内完成的基本运算的次数=64*3*2^n=2^6*3*2^n=3*2^(n+6)～T=T(n)=3*2^nn=log2(T/3)～设新机器输入规模为n1,则：～n1=log2(3*2^(n+6)/3)=n+6～在这台新机器上用同一算法在t秒内能解输入输入规模为n+6的问题。3.试说明为什么“在现代计算机上运行指数（如2n）时间算法是不可能的，要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法计算复杂度的数量级，而不是提高计算机的速度”。（8分）一个计算时间为Ο(1)的算法，它的基本运算执行的次数是固定的，因此，总的时间由一个常数(即，零次多项式)来限界，而一个时间为Ο(n2)的算法则由一个二次多项式来限界。以下六种计算时间的多项式时间算法是最为常见的，其关系为指数时间算法一般有Ο(2n)、Ο(n!)和Ο(nn)等。其关系为其中，最常见的是时间为Ο(2n)的算法。当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊，因为根本就找不到一个这样的m，使得2n囿界于nm。换言之，对于任意的m≥0，总可以找到n0，当n≥n0时，有2n＞nm。因此，只要有人能将现有指数时间算法中的任何一个算法简化为多项式时间算法，那就取得了一个伟大的成就。Ο(log2n)、Ο(n)和Ο(nlog2n)比另外三种时间函数的增长率慢得多。～由这些结果可看出，当数据集的规模(即n的取值)很大时，要在现代计算机上运行具有比Ο(nlog2n)复杂度还高的算法往往是很困难的。尤其是指数时间算法，它只有在n值取得非常小时才实用。要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度的数量级，而不是提高计算机的速度。二、简答（共21分）1.对计算复杂性的研究能够使人们弄清所求解问题的固有难度，并得出评价某类算法优劣的准则，用以指导设计出更高效的算法。试用简短的语言说明“建立一个问题复杂性的下界要比确定它的上界困难得多！”其复杂性上界是已知求解该问题的最快算法的费用，而复杂性下界只能通过理论证明来建立。寻求某个问题的计算复杂性上界，只要研究一个算法的复杂性即可。但是要寻求同一问题的计算复杂性下界，则必须考察所有的解决该问题的算法，证明一个问题的复杂性下界就需要证明不存在任何复杂性低于下界的算法。显然，建立下界要比确定上界困难得多。2.满足何种性质的问题被称为称为NP完全问题？请简述研究NP完全问题的意义；（1）NP即是多项式复杂程度的非确定性问题。而如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题。如果一个NP完全问题能在多项式时间内得到解决，那么NP中的每一个问题都可以在多项式时间内解决。（2）NP完全是指这样一类NP问题,所有的NP问题都可以用多项式时间划归到他们中的一个.所以显然NP完全的问题具有如下性质:它可以在多项式时间内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。这样一来,只要我们找到一个NPC问题的多项式解,所有的NP问题都可以多项式时间内划归成这个NPC问题,再用多项式时间解决,这样NP就等于P了.NP完全性理论的重要性:知道一个问题是NP完全的就给我们提供了有价值的信息，告诉我们采用什么样的途径可以是最富有成效的。一定不要去优先寻找有效的、精确的算法。现在比较适当的途径是集中精力致力于其他较低目标的方法。例如，你可以寻找解决这个问题的各种特殊情况的有效算法。寻找在大多数情况下看来能快速运算的算法，虽然不能保证它在任何情况下都能快速地运算。或者你甚至可以放松问题的某些方面，寻找一个只能给出满足大部分要求的快速算法。简言之，NP完全性理论的初步应用是帮助算法设计人员找到最有可能得到有用的算法的努力方向。3.“当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质”。问题的最优子结构性质是该问题可用动态规划算法求解的基本要素，试简要阐述“论证某一问题的最优子结构性质”时的一般方法；当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。在分析问题的最优子Ο(2n)＜Ο(n!)＜Ο(nn)Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(nn)结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。（动态规划算法）利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。三、算法设计与分析问题1.最大值和最小值问题的最优算法（18）给定n个实数存放于一维数组A中，试设计一个算法在最坏情况下用3n/2-2次的比较找出A中的最大值和最小值（为简化，可假设n为偶数）。voidMaxMin(intlength){intMax,Min;int[]big,small;big=newint[length/2];//用来存放较大的数small=newint[length/2];//用来存放较小的数for(inti=0,j=0;ilength-1;i+=2,j++)//数组中的数两两相比，较大的存入big[],较小的存入small[]，比较length/2次{if(a[i]=a[i+1]){big[j]=a[i];small[j]=a[i+1];}else{small[j]=a[i];big[j]=a[i+1];}}Max=big[0];Min=small[0];for(inti=1;ibig.length;i++)//找到最大值，比较length/2次{if(Maxbig[i])Max=big[i];}for(inti=1;ismall.length;i++)//找到最小值，比较length/2次{if(Minsmall[i])Min=small[i];}}由于成对处理，总的循环次数为n/2，而每次循环进行3次比较，总比较次数就是3n/2次。奇数时3n/2-2次的比较【Fori=1-kifA[i]A[i+k]swap(i,i+k)】2.社会名流问题在n个人中，一个被所有人知道但却不知道别人的人，被定义为社会名流。现在的问题是如果存在，试找出该社会名流。你可以使用的唯一方式是询问：“对不起，请问你知道那个人吗？”（假定所有回答都正确，甚至这位社会名流也将回答。）我们的最终目标是将询问的数目最小化。试设计表达社会名流问题的数据结构(提示：利用有向图表示这n个人之间的关系)，并在此基础上设计问题求解的算法。（20分）给定一个n×n邻接矩阵，确定是否存在一个i，其满足在第i列所有项（除了第ii项）都为1，并且第i行所有项（除了第ii项）都为0。大致的算法思路：随便取一个非对角线元素，比如Array[i][j]，如果Array[i][j]=0成立，则j不是社会名流，于是删去第j行和第j列。同样，如果Array[i][j]=1成立，则删去第i行和第i列；总之，无论对应项取何值，都可以删去一行和一列，因此整个操作只耗费O(n)的时间。重复此操作直至剩下最后一个元素。最后，检验该元素是否为社会名流即可。如果该元素不是，则该群人中不存在社会名流。3.数列极差问题（17分）在黑板上写了N个正数组成的一个数列，进行如下的操作：每一次任选其中的两个数设为a和b，将其擦去，然后在数列中加入一个新的数a*b+1，如此下去直至黑板上只剩下一个数为止。在所有按这种操作方式最后得到的数中，最大的数记为Max，最小的数记为Min，则该数列的极差定义为M=Max-Min。试为按上述方法求解“数列极差”设计算法(此题不要求用伪码描述—只需写出实现的思想与理由)。设有三个数xyz,且xyz，按问题描述来做的话，结果有下面三种情况：num1=（x*y+1）*z+1=xyz+z+1,num2=(x*z+1)*y+1=xyz+y+1，num3=(y*z+1)*x+1=xyz+x+1。很容易看出num1num2num3。～所以我们可以得出结论：优先选择数列中最小的2个数进行（a*b+1）运算得到的值大，优先选择数列中最大的2个数进行（a*b+1）运算得到的值小。我们可以把整体的MAX，MIN值通过一系列局部求MAX,MIN值来求我们想要的结果。我们在看下用贪心策略求解的合理性：～假设经（N－3）次运算后得到3个数：xymax（maxxy），～其中max是（N－2）个数经（N－3）次运算后所得的最大值，～此时最大值m＝（x*y＋1）×max＋1。～若经（N－2）次变换后所得的3个数为：xyz（zxy）且z不为（N－2）次变换后的最大值，～即z＜max则所求得的最大值为：m’＝（x*y+1）*z+1，～此时m－m’＝（1+x*y）（max－z）＞0所以此时不为最优解。～所以若使第k（1≤k≤N－1）次变换后所得值最大，必使（k－1）次变换后所得值最大（符合贪心策略的最优子结构性质），在进行第k次变换时，只需取在进行（k－1）次变换后所得数列中的两最小数x，y进行运算，再把结果插入到数列即可。另：使用一个快速排序的迭代模型可以使原递归算法所需的栈空间总量减至O（logn）。试设计这一迭代模型structnode{intlow,high;}st[10000];voidquicksort2(intdata[],ints,intt){inttop=-1,low,high;top++;st[top].low=s;st[top].high=t;while(top-1){low=st[top].low;high=st[top].high;top--;intw;if(lowhigh){w=split(data,low,high);//或者split2st[++top].low=low;st[top].high=w-1;st[++top].low=w+1;st[top].high=high;}}