习题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'^
