第1章 算法概述_作业-1.5

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,课后练习：算法分析题,1-1 求下列函数的渐近表达式：,1-2 试论,O(1),和,O(2),的区别。,解答：,根据符号,O,的含义，,O(1)=O(2),，,当用,O(1),与,O(2),表示常数阶的渐近函数时，差别仅在于其中的常数因子。,1-3 按照渐近阶从低到高的顺序排列以下表达式：,1-4 假设某算法在输入规模为,n,时的计算时间为,T(n)=32,n,。,在某台计算机上实现并完成该算法的时间为,t,秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在,t,秒内能解输入规模多大的问题？,若上述算法的计算时间改进为,T(n)=n,2,，,其余条件不变，则在新机器上用,t,秒时间能解输入规模为多大的问题？,若上述算法的计算时间进一步改为,T(n)=8，,其余条件不变，那么在新机器上用,t,秒时间能解输入规模多大的问题？,（,1,）设新机器用同一算法能够解输入规模为,n1,的问题，因此,t=3*2,n,=3*2,n1,/64,，,解得，,n1=n+6,。,（,2,）,n1,2,=64n,2,，,解得，,n1=8n,。,（,3,）,因为,T(n)=8,，,为常数，因此,算法可以解任意规模的问题,。,1-6 对于下列各组函数,f(n),和,g(n)，,确定,f(n)=O(g(n),或,f(n)=(g(n),或,f(n)=(g(n)，,并简述理由。,logn,2,=(logn+5),logn,2,=O(n,1/2,),n=(log,2,n),nlogn+n=(logn),10=,(log10),log,2,n+n=(logn),2,n,=(100n,2,),2,n,=O(3,n,),End,