习题2-1 求下列函数的渐进表达式： 3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。 解答：3n^2+10n=O(n^2), n^2/10+2^n=O(2^n), 21+1/n=O(1), logn^3=O(logn), 10log3^n=O(n). 习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。 解答：照渐进阶从高到低的顺序为：n!、 3^n、4n^2 、20n、n^2/3、logn、2 习题2-4 (1)假设某算法在输入规模为n 时的计算时间为T(n)=3*2^n。在某台计算机上实现并完成该算法的时间为t 秒。现有另外一台计算机，其运行速度为第一台计算机的64 倍，那么在这台新机器上用同一算法在 t 秒内能解输入规模为多大的问题？ (2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用 t 秒时间能解输入规模多大的问题？ (3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用 t 秒时间能解输入规模多大的问题？ 解答：(1)设能解输入规模为n1 的问题，则 t=3*2^n=3*2^n/64, 解得 n1=n+6 (2)n1^2=64n^2 得到n1=8n (3)由于 T（n)=常数，因此算法可解任意规模的问题。 习题2-5 XYZ 公司宣称他们最新研制的微处理器运行速度为其竞争对手 ABC 公司同类产品的100 倍。对于计算复杂性分别为n，n^2，n^3 和 n!的各算法，若用 ABC 公司的计算机能在 1 小时内能解输入规模为n 的问题，那么用 XYZ 公司的计算机在 1 小时内分别能解输入规模为多大的问题？ 解答：n'=100n n'^2=100n^2 得到n'=10n n'^3=100n^3 得到n'=4.64n n'!=100n!得到n'
