算法设计与分析,王晓东,实验报告.doc

算法设计与分析,王晓东,实验报告 算法设计与分析王晓东 习题2-1 求下列函数的渐进表达式： 3n+10n; n/10+2n; 21+1/n; logn; 10 log3 。 解答：3n+10n=O(n), n/10+2=O(2), 21+1/n=O(1), logn=O(logn), 10log3=O(n). 习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n,logn,3,20n,2,n/3。 解答：照渐进阶从高到低的顺序为：n!、 3、4n 、20n、n/3、logn、2 习题2-4 (1)假设某算法在输入规模为n时的计算时间为T(n)=3*2。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？ (2)若上述算法的计算时间改进为T(n)=n，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？ (3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？ 解答：(1)设能解输入规模为n1的问题，则t=3*2=3*2/64,解得n1=n+6 (2)n1=64n得到n1=8n (3)由于T（n)=常数，因此算法可解任意规模的问题。 习题2-5XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n，n和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？ 解答：n#39;=100n n#39;=100n得到n#39;=10n n#39;=100n得到n#39;=4.64n n#39;!=100n!得到n#39;n+log100=n+6.64 习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。 解答：（1）f(n)=logn;g(n)=logn+5. logn=θ（logn+5） (2)f(n)=logn;g(n)=根号n. logn=O(根号n) (3)f(n)=n;g(n)=(logn). n=Ω(（logn）) (4)f(n)=nlogn+n;g(n)=logn. nlogn+n=Ω（logn） (5)f(n)=10;g(n)=log10. 10=θ(log10) (6)f(n)=(logn);g(n)=logn. (logn)=Ω（logn） (7)f(n)=2;g(n)=100n. 2=Ω（100n） (8)f(n)=2;g(n)=3. 2=O(3) 习题2-7 证明：如果一个算法在平均情况下的计算时间复杂性为θ（f(n)），则该算法在最坏情况下所需的计算时间为Ω（f(n)）。 证明：Tavg(N)=IeDn∑P(I)T(N,I) ≤IeDn∑P(I)IeDnmaxT(N,I#39;) =T(N,I*)IeDn∑P(I) =T(N,I*)=Tmax(N) 第三章 递归与分治策略 习题3-1 下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明。 public static int binarySearch1(int []a,int x,int n) { int left=0; int right =n-1; while (left=right) { int middle = ( left + right )/2; if ( x == a[middle]) return middle; if ( x a[middle]) left = middle; else right = middle; return -1; } public static int binarySearch2(int []a, int x, int n) { int left = 0; int right = n-1; while ( left right-1 ) { int middle = ( left + right )/2; if ( x a[middle]) right = middle; else left = middle; } if (x == a[left]) return left; else return -1 } p