严蔚敏版数据结构课后习题答案-完整版 下载本文

(7) ?n? 向下取整 (8) 1100

1.9 假设n为2的乘幂,并且n>2,试求下列算法的时间复杂度及变量count的值(以n的函数形式表示)。 int Time(int n) {

count = 0; x=2; while(x

return count;

}

解:o(log2n) count=log2n?2

1.11 已知有实现同一功能的两个算法,其时间复杂度分别为O?2n?和

On10,假设现实计算机可连续运算的时间为107秒(100多天),又每

x *= 2; count++;

??秒可执行基本操作(根据这些操作来估算算法时间复杂度)105次。试问在此条件下,这两个算法可解问题的规模(即n值的范围)各为多少?哪个算法更适宜?请说明理由。

解:2n?1012

n=40

n=16

n10?1012

则对于同样的循环次数n,在这个规模下,第二种算法所花费的代价要大得多。故在这个规模下,第一种算法更适宜。

1.12 设有以下三个函数:

f?n??21n4?n2?1000,g?n??15n4?500n3,h?n??500n3.5?nlogn 请判断以下断言正确与否: (1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n3.5) (5) h(n)是O(nlogn)

解:(1)对 (2)错 (3)错 (4)对 (5)错

1.13 试设定若干n值,比较两函数n2和50nlog2n的增长趋势,并确定n在什么范围内,函数n2的值大于50nlog2n的值。

解:n2的增长趋势快。但在n较小的时候,50nlog2n的值较大。

当n>438时,n2?50nlog2n

1.14 判断下列各对函数f?n?和g?n?,当n??时,哪个函数增长更快? (1) f?n??10n2?lnn!?10n,g?n??2n4?n?7

3??(2) f?n???ln?n!??5?2,g?n??13n2.5 (3) f?n??n2.1?n4?1,g?n???ln?n!??2?n (4) f?n??2?n???2n?,g?n??n?n??n5

322解:(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 1.15 试用数学归纳法证明: (1) ?i2?n?n?1??2n?1?/6

i?1n?n?0?