算法设计与分析练习题

《算法设计与分析练习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析练习题1.仅使用Ο、Ω、Θ和o的定义，证明下列各式成立。1)5n2–6n=Θ(n2)2)n!=Ο(nn)ni=0∑3)2n22n+nlogn=Θ(n22n)ni=0∑4)i2=Θ(n3)n2n（n）2n5)i3=Θ(n4)6)+6*2n=Θ7)n3+106n2=Θ(n3)8)6n3/(logn+1)=Ο(n3)9)n1.001+nlogn=Θ(n1.001)10)nk+ε+nklogn=Θ(nk+ε)，k≥0，ε＞02.采用定理2.2、2.4和2.6，证明第1题的所有式子成立。3.证明以下等式不成立。1)10n2+9=Ο(n)2)n2logn=Θ(n2)3)n2/logn=

2、Θ(n2)4)n32n+6n23n=Ο(n32n)n→∞4.证明当且仅当limf(n)/g(n)=0时，f(n)=o(g(n))。5.下面哪些规则是正确的？为什么？1){f(n)=Ο(F(n))，g(n)=Ο(G(n))}→f(n)/g(n)=Ο(F(n)/G(n))2){f(n)=Ο(F(n))，g(n)=Ο(G(n))}→f(n)/g(n)=Ω(F(n)/G(n))3){f(n)=Ο(F(n))，g(n)=Ο(G(n))}→f(n)/g(n)=Θ(F(n)/G(n))4){f(n)=Ω(F(n))，g(n)=Ω(G(n))}→f(n)/g(n)=Ω(F(n)/G(n))5){f(n)

3、=Ω(F(n))，g(n)=Ω(G(n))}→f(n)/g(n)=Ο(F(n)/G(n))6){f(n)=Ω(F(n))，g(n)=Ω(G(n))}→f(n)/g(n)=Θ(F(n)/G(n))1){f(n)=Θ(F(n))，g(n)=Θ(G(n))}→f(n)/g(n)=Θ(F(n)/G(n))2){f(n)=Θ(F(n))，g(n)=Θ(G(n))}→f(n)/g(n)=Ω(F(n)/G(n))3){f(n)=Θ(F(n))，g(n)=Θ(G(n))}→f(n)/g(n)=Ο(F(n)/G(n))6．计算以下函数的渐进复杂性，设计一个频率表加以说明。1).SelectionSort(

4、a[],intn)语句s/e频率总步数VoidSelectionSort(elemTyoea[],intn){//及时终止的选择排序boolSorted=false;for(intsize=n;!sorted&&(size>1);size--){intpos=0;sorted=true;for(inti=1;i

5、rt(elemTyoea[],intn){//及时终止的选择排序for(inti=1;i=0&&ta[i+1]

6、){Swap(a[i],a[i+1]);swapped=true;//发生了交换};returnswapped;}voidBubbleSort(elemTyoea[],intn){//及时终止的冒泡排序算法for(inti=n;i>1&&Bubble(a,i);i--);}总计4)判断下列算法的渐进时间复杂度StatusCharLoopCheck(){InitStack(S);InitQueue(Q);C=getchar();//读取一个字符。或者从文件上读入；或者从键盘上读入。While(c!=’@’){Push(S,c);EnQueue(Q,c);C=getchar();};//wh

7、ilewhile(!empty(s)){pop(s,x);Dequeue(Q,y);if(x!=y)return‘Error’;};whileif(!empty(s)

8、

9、!empty(Q)){return‘Error’;}elsereturn‘ok’}//CharLoopCheck7.某算法的计算时间可用下面的递推关系式描述。试采用迭代的方式求解该关系式，并用大写О表示解(要求给出详细的推导过程)。an=1，a为常数T(n)=2T(