算法分析习题

算法分析习题1.按照增长率从低到高的顺序排列以下表达式：4n!20n22.（a）假设某一算法的时间代价为T（n）=3，对于输入规模n,在某台计算机上实现并完成该算法的时间为T秒。现在另有一台计算机，运行速度为第一台的64倍，那么T秒内新机器上能完成问题的输入规模是多少？（b）假设又有一种算法，T（n）=,其余条件不变，那么新机器T秒内能完成的输入规模是多少？（c）若算法T(n)=8n,其余条件不变，那么在新机器上T秒内能够处理多少输入数据？3.写出下列程序段平均情况下时间代价的表达式。假设所有变量类型都为int：（a）a=b+c;d=a+e;(b)sum=0;for(i=0;i3;i++)for(j=0;jn;j++)sum++;(c)sum=0;for(i=0;inn;i++)sum++;(d)假设数组A中含有n个元素，函数Random花的时间是常量，sort需要执行n步。For(i=0;in;i++){For(j=0;jn;j++)A[i]=Random(n);Sort(A,n);}(e)假设数组A中元素为从0到n-1的任意一个排列。Sum3=0；For(i=0;in;i++)For(j=0;A[j]!=i;j++)Sum3++；(f)sum=0;If(EVEN(n))For(i=0;in;i++)Sum++;ElseSum=sum+n;