计算机算法分析与设计——王晓东（第二版）第一章课后习题

习题1(详细解析版)

1-1

Q：

A：

思路：因为要求函数的渐进表达式，所以就是找函数表达式的最高阶来代表整个式子。

（1）很明显，幂函数，2次大于1次

所以：3n^2 + 10n = O(n ^ 2)

（2）当n很大时，2 ^ n远远大于n ^ 2

n ^ 2 /10 + 2 ^ n = O(2 ^ n)

（3）n很大时，1/n会很小，所以保留21，是常数阶，这里写成O(1)

21 + 1 / n = O(1)

（4）利用对数函数的性质：

所以这里：log (n ^ 3) = 3 log n

所以log (n^3) = 3logn = O(log n)

（5）利用对数函数性质，得：

10 log(3 ^ n) = (10log3)n= O(n)

1-2

Q:

A:

都表示常数规模，本质是O(1) = O(2)

1-3

Q:

A:

从4*(n^2)开始，从左到右依次对应下面图像中的a、b、c、d、e、f

1-4

Q:

A:

按照渐进阶从低到高顺序进行排列，依次为2 logn n^(2/3) 20n 4*(n ^ 2) 3 ^n n!

1-5

Q:

A:

这里的关键在于T（n）的理解，我是这么理解的。题目中说：某算法在输入规模为n时的计算时间为T（n）=3 x 2^n ， 这个T（n）是时间关于问题规模n的函数，计算时间会随着问题规模n的增大而按这个式子增大。也就是说，这个T（n）其实代表的是这个算法的性能，是当前算法的固有属性。

（1）

我们通过时间建立等价关系。

因为规定的时间都是t,设新机器能在t时间内解问题规模为n1大的问题。

64 * 3 x 2^n = 3 x2 ^ n1

所以n1 = n + 6

（2）

这里改变了T（n），其实相当于改变了算法的固有属性，还是一样的，根据时间t建立等价关系。

设在新机器上用t秒时间能解输入规模为n2大的问题。

64 * (n ^ 2) = n2 ^ 2

n2 = 8n

（3）当算法改进为T（n）= 8

设新机器上用t秒时间能解输入规模为n3大的问题。

因为T(n) = 8，说明了这是一个常数级的算法，所以n3可以为任意规模。

1-6

Q：

A：

因为微处理器的运行速度快了，所以就是计算机的计算速度快了，计算机的性能变强了。

（1）设用XYZ公司的计算机在1小时内能解输入规模为n1大的问题。

n1 = 100n

（2）设用XYZ公司的计算机在1小时内能解输入规模为n2大的问题。

n2 ^ 2 = 100 * n^2

得n2 = 10n

（3）设用XYZ公司的计算机在1小时内能解输入规模为n3大的问题。

n3 ^ 3 = 100 (n ^ 3)

得：

1-7

Q：

A:

所以得：

1-8

Q:

A:

1-9

Q:

A:

该算法是著名的3n + 1问题。

最好的情况是，n为2的次方，之后进入程序，n一直在折半，所以时间下界为

O（logn）

该算法没有上界。

1-10

Q：

A：这道题我还没有学会，呜呜呜呜…