算法设计与分析练习题VIP专享VIP免费

算法设计与分析练习题1. 仅使用 Ο、Ω、Θ 和 o 的定义，证明下列各式成立。1) 5n2 – 6n = Θ(n2)2) n!= Ο(nn)3) 2n22n + nlogn =Θ(n22n)4) i2 = Θ(n3)5) 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 =Θ(n2)4) n32n+6n23n=Ο(n32n)4. 证明当且仅当 lim f(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)=Ω(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))7) {f(n)=Θ(F(n))，g(n)=Θ(G(n))} → f(n)/g(n)=Θ(F(n)/G(n))8) {f(n)=Θ(F(n))，g(n)=Θ(G(n))} → f(n)/g(n)=Ω(F(n)/G(n))9) {f(n)=Θ(F(n))，g(n)=Θ(G(n))} → f(n)/g(n)=Ο(F(n)/G(n))6．计算以下函数的渐进复杂性，设计一个频率表加以说明。1).SelectionSort(a[],int n)语句s/e频率总步数Void SelectionSort(elemTyoe a[],int n) {//及时终止的选择排序bool Sorted = false;for(int size = n;!sorted&&(size>1);size--){n→∞（n ）2nn2nni=0∑ni=0∑int pos = 0;sorted = true;for(int i=1;i=0 && t