数据结构、算法与应用(C++描述)(第二版)第三章习题解答
2021-05-12 20:28
标签：lan sid return init 应用 href indexof frequency max 官方：[https://www.cise.ufl.edu/~sahni/dsaac/chapter3.htm] 数据结构、算法与应用(C++描述)(第二版)第三章习题解答 标签：lan sid return init 应用 href indexof frequency max 原文地址：https://www.cnblogs.com/ysjcqs/p/DataChapter3.html1
(a)
lim n -> infinity (q(n) / p(n))
= lim n -> infinity (100n2 + 6)/(3n4 + 2n2)
= lim n -> infinity (100/n2 + 6/n4)/(3 + 2/n2)
= 0/3
= 0
(c)
lim n -> infinity (q(n) / p(n))
= lim n -> infinity 10n2/(7n2log n)
= lim n -> infinity (10/log n)/7
= 0/7
= 0
2
(a)
O(n3)
(c)
O(n2log n)
(e)
O(n2n)
3
(a)
2n + 7渐近地大于1。因此，2n + 7 != O(1)。
(c)
5n3 + 6n2渐近大于n2。因此，5n3 + 6n2 != O(n2)。
4
(a)
Omega(n3)
(c)
Omega(n2log n)
(e)
Omega(n2n)
5
(a)
2n + 7渐近地小于n2。因此，2n + 7 != (n2)
(c)
5n3 + 6n2渐近小于n3log n，因此，5n3 + 6n2 != (n3log n)
6
(a)
Theta(n3)
(c)
Theta(n2log n)
(e)
Theta(n2n)
7
(a)
t(n) = Theta(1)
(c)
t(n) = Theta(n2)
(e)
t(n) = Omega(n3)
(g)
t(n) = Theta(n2)
8
(a)
Theta(m2n2+m3n)
(c)
Theta(m4+n3+m3n2)
9
(a)
5n2 - 6n = 1. So, 5n2 - 6n = O(n2). Also, 5n2 - 6n >= 5n2 - n2 = 4 n2 for n >= 6. So, 5n2 - 6n = Omega(n2). Consequently, 5n2 - 6n = Theta(n2).
(c)
f(n) = 2n22n + n log n = 1. So, f(n) = O(n22n). Also, f(n) >= 2n22n for n >= 1. So, f(n) = Omega(n22n). Therefore, f(n) = Theta(n22n).
(e)
f(n) = sum from (i=0) to n i3 = 1. So, f(n) = O(n4). Also, f(n) >= sum from (i=ceil(n/2)) to n i3 >= sum from (i=ceil(n/2)) to n (n/2)3 = (n - ceil(n/2) + 1)(n/2)3 >= n4/16 for n >= 1. So, f(n) = Omega(n4). As a result, f(n) = Theta(n4).
(g)
f(n) = n3 + 106n2 = 106. Also, f(n) 0. So, f(n) = Theta(n3).
10
(a)
(5n2 - 6n) / n2 = 5 - 6 / n which is 11
(a)
f(n) / g(n) = 10n + 9 / n which goes to infinity as n goes to infinity. So, f(n) is not O(g(n)).
(c)
g(n) / f(n) = log n which goes to infinity as n goes to infinity. So, f(n) is not Theta(g(n)).
13
If f(n) = Omega(g(n)), then there exist a positive c and an n0 such that g(n)/f(n) = n0. Hence, the limit of g(n)/f(n) as n goes to infinity is = n0. This proves Theorem 3.4. Theorems 3.2 and 3.4 together imply Theorem 3.6.
15
(E5)
(sum from 1 to n)ik = (sum from n/2 to n)(n/2)k = (n/2)k+1. Therefore, (sum from 1 to n)ik = Omega(nk+1). (Note that 2k+1 is a constant as k is a constant.) Consequently, (sum from 1 to n)ik = Theta(nk+1).
(E6)
(sum from 1 to n)ri = (rn+1-1)/(r-1) - 1 = Theta(rn). From this it follows that (sum from 1 to n)ri = O(rn) and (sum from 1 to n)ri = Omega(rn).
17
(a)
Not true. For example, if f(n) = n2 and g(n) = 1, then f(n) = O(n2) and g(n) = O(n2). But, f(n)/g(n) = n2 != O(1).
(b)
Not true. For example, if f(n) = n2 and g(n) = n2, then f(n) = O(n4) and g(n) = O(n2). But, f(n)/g(n) = 1 != Omega(n2).
(c)
Not true. Follows from (a) and/or (b).
(d)
Not true. For example, if f(n) = n2 and g(n) = n2, then f(n) = Omega(n2) and g(n) = Omega(1). But, f(n)/g(n) = 1 != Omega(n2).
(e)
Not true. For example, if f(n) = n2 and g(n) = 1, then f(n) = Omega(1) and g(n) = Omega(1). But, f(n)/g(n) = n2 != O(1).
(f)
Not true. Follows from (d) and/or (e).
18
(a)
_________________________________________________________________________________________
Statement s/e Frequency Total steps
_________________________________________________________________________________________
int factorial(int n) 0 0 Theta(0)
{ 0 0 Theta(0)
if (n 1 (here c is a constant). Using repeated substitution, we get:
tfactorial(n) = 1 + tfactorial(n-1)
= 2 + tfactorial(n-2)
= 3 + tfactorial(n-3)
.
.
.
= n - 1 + tfactorial(1)
= n - 1 + c
= Theta(n)
(c) We shall do the analysis for the case n >= 1.
_______________________________________________________________________________________
Statement s/e Frequency Total steps
_______________________________________________________________________________________
bool minmax(...) 0 0 Theta(0)
{ 0 0 Theta(0)
if (n a[i]) indexOfMin = i; 1 Theta(n) Theta(n)
else if (a[indexOfMax] ...) indexOfMax = i; 1 Omega(0), O(n) Omega(0), O(n)
return true; 1 1 Theta(1)
} 0 0 Theta(0)
_______________________________________________________________________________________
So, tminmax(n) = Theta(n), n >= 1.
(f)
_______________________________________________________________________________
Statement s/e Frequency Total steps
_______________________________________________________________________________
void matrixMultiply(...) 0 0 Theta(0)
{ 0 0 Theta(0)
for (int i = 0; i = 1.
___________________________________________________________________________________
Statement s/e Frequency Total steps
___________________________________________________________________________________
T polyEval(...) 0 0 Theta(0)
{ 0 0 Theta(0)
T y = 1, ...; 1 1 Theta(1)
for (int i = 1; i = 1.
(j)
__________________________________________________________________________________________
Statement s/e Frequency Total steps
__________________________________________________________________________________________
void rank(...) 0 0 Theta(0)
{ 0 0 Theta(0)
for (int i = 0; i 1; size--) 1 Theta(n) Theta(n)
{ 0 0 Theta(0)
int j = indexOfMax(a, size); Theta(size) Theta(n) Theta(n2)
swap(a[j], a[size - 1]); 1 Theta(n) Theta(n)
} 0 0 Theta(0)
} 0 0 Theta(0)
________________________________________________________________________________
So, tselectionSort (n) = Theta(n2)
(n) First, we obtain the asymptotic complexity of insert.
_________________________________________________________________________________
Statement s/e Frequency Total steps
_________________________________________________________________________________
void insert(...) 0 0 Theta(0)
{ 0 0 Theta(0)
int i; 0 0 Theta(0)
for (i = n - 1; i >= 0 && ...) 1 Omega(1), O(n) Omega(1), O(n)
a[i+1] = a[i]; 1 Omega(1), O(n) Omega(1), O(n)
a[i+1] = x; 1 1 Theta(1)
} 0 0 Theta(0)
_________________________________________________________________________________
So, tinsert(n) = Omega(1), O(n)
Now, we analyze the function insertionSort.
____________________________________________________________________________________
Statement s/e Frequency Total steps
____________________________________________________________________________________
void insertionSort(...) 0 0 Theta(0)
{ 0 0 Theta(0)
for (int i = 1; i 1; i--) 1 Theta(n) Theta(n)
bubble(a, i); Theta(i) Theta(n) Theta(n2)
} 0 0 Theta(0)
_______________________________________________________________________________
So, tbubbleSort (n) = Theta(n2)
19
(a)
Program A is faster than program B when 1000n 100.
(b)
Program A is faster than program B when 2n2 2.
(c)
Program A is faster than program B when 2n 1000 log2n. The switchover point is between 213 and 214.
21
For tA(n) = n, the table entries are xN = 10N, 100N, 1000N, and 1000000N.
For tA(n) = n2, the table entries are sqrt(x)N, for tA(n) = n3, the table entries are x1/3N, and for tA(n) = n5, the table entries are x1/5N.
For tA(n) = 2n, the table entries are log2x N,
下一篇：算法分析与设计——各类排序算法
文章标题：数据结构、算法与应用(C++描述)(第二版)第三章习题解答
文章链接：http://soscw.com/index.php/essay/84837.html