目录
第三章 函数的增长
3-1 知识点
Θ \Theta Θ记号
Θ ( g ( n ) ) \Theta(g(n)) Θ(g(n))的含义为：存在正常量 c 1 , c 2 和 n 0 c_1,c_2 和 n_0 c1,c2和n0，使得对所有 n ≥ n 0 n \ge n_0 n≥n0，有 0 ≤ c 1 g ( n ) ≤ f ( n ) ≤ c 2 g ( n ) 0 \le c_1g(n) \le f(n) \le c_2g(n) 0≤c1g(n)≤f(n)≤c2g(n)。
举个例子，当分析插入排序的最坏运行时间时：
- f ( n ) = a 2 n 2 + b n + c f(n) =\frac{a}{2}n^2 + bn +c f(n)=2an2+bn+c
- g ( n ) = n 2 g(n) = n^2 g(n)=n2
在算法导论一书中，通常使用 f ( n ) = Θ ( g ( n ) ) f(n) = \Theta(g(n)) f(n)=Θ(g(n)) 来表示与 f ( n ) ∈ Θ ( g ( n ) ) f(n) ∈ \Theta(g(n)) f(n)∈Θ(g(n)) 相同的含义，即 Θ ( g ( n ) ) \Theta(g(n)) Θ(g(n))代表一个集合， f ( n ) f(n) f(n)代表一个属于 Θ ( g ( n ) ) \Theta(g(n)) Θ(g(n))的函数。
O \Omicron O记号
O ( g ( n ) ) \Omicron(g(n)) O(g(n))的含义为：存在正常量 c c c 和 n 0 n_0 n0，使得对所有 n ≥ n 0 n\ge n_0 n≥n0，有 0 ≤ f ( n ) ≤ c g ( n ) 0 \le f(n) \le cg(n) 0≤f(n)≤cg(n)。
f ( n ) = O ( g ( n ) ) f(n) = \Omicron(g(n)) f(n)=O(g(n)) 一般用来表示 g(n) 的某个常量倍数是 f(n) 的渐进上界，而不要求它是一个多么紧确的上界。比如, n = O ( n 2 ) , n 2 = O ( n 2 ) n = O(n^2), n^2 = O(n^2) n=O(n2),n2=O(n2)都是成立的。
当我们说运行时间为 O ( n 2 ) \Omicron(n^2) O(n2) 时，意指其最坏情况运行时间为 O ( n 2 ) \Omicron(n^2) O(n2)。
Ω \Omega Ω记号
Ω ( g ( n ) ) \Omega(g(n)) Ω(g(n)) 的含义为：存在正常量 c c c 和 n 0 n_0 n0，使得对所有 n ≥ n 0 n\ge n_0 n≥n0，有 0 ≤ c g ( n ) ≤ f ( n ) 0 \le cg(n) \le f(n) 0≤cg(n)≤f(n)
不是所有函数都可渐进比较
设
f
(
n
)
=
n
，
g
(
n
)
=
n
1
+
sin
x
f(n) = n，g(n) = n^{1+\sin x}
f(n)=n，g(n)=n1+sinx，则
f
(
n
)
=
O
(
g
(
n
)
)
，
f
(
n
)
=
Ω
(
g
(
n
)
)
f(n) = \Omicron(g(n))，f(n) = \Omega(g(n))
f(n)=O(g(n))，f(n)=Ω(g(n)) 都不成立。f(n) 与 g(n) 的函数图像如下：
练习题
3.1-1
假设 f(n) 和 g(n) 都是渐进非负函数，证明 m a x ( f ( n ) , g ( n ) ) = Θ ( f ( n ) + g ( n ) ) max(f(n), g(n)) = \Theta(f(n) + g(n)) max(f(n),g(n))=Θ(f(n)+g(n))。
因为两者均为渐进非负函数，所以存在正常量 n 0 n_0 n0，使得对所有 n ≥ n 0 n \ge n_0 n≥n0，都有 f ( n ) > = 0 , g ( n ) > = 0 f(n) >= 0, g(n) >= 0 f(n)>=0,g(n)>=0。取 c 1 = 1 2 ， c 2 = 3 2 c_1 = \frac{1}{2}，c_2=\frac{3}{2} c1=21，c2=23，则对所有 n ≥ n 0 n \ge n_0 n≥n0，都有：
c 1 ∗ m a x ( f ( n ) , g ( n ) ) ≤ f ( n ) + g ( n ) ≤ c 2 ∗ m a x ( f ( n ) , g ( n ) ) c_1*max(f(n), g(n)) \le f(n) + g(n) \le c_2*max(f(n),g(n)) c1∗max(f(n),g(n))≤f(n)+g(n)≤c2∗max(f(n),g(n))
综上， m a x ( f ( n ) , g ( n ) ) = Θ ( f ( n ) + g ( n ) ) max(f(n), g(n)) = \Theta(f(n) + g(n)) max(f(n),g(n))=Θ(f(n)+g(n))
其实， c 1 ， c 2 c_1，c_2 c1，c2 有很多选择，但重要的时存在这样的选择。
3.1-2
证明：对任意实常量 a，b，其中 b > 0，有 ( n + a ) b = Θ ( n b ) (n+a)^b = \Theta(n^b) (n+a)b=Θ(nb)
为了证明上述结论，需找到正常量 c 1 , c 2 , n 0 c_1,c_2,n_0 c1,c2,n0 ，使得对所有 n ≥ n 0 n \ge n_0 n≥n0时，都有 0 ≤ c 1 ∗ n b ≤ ( n + a ) b ≤ c 2 ∗ n b 0 \le c_1*n^b \le (n+a)^b \le c_2*n^b 0≤c1∗nb≤(n+a)b≤c2∗nb。
当 n 0 = 2 ∗ ∣ a ∣ n_0 = 2*|a| n0=2∗∣a∣ 时，无论 a 取何值，下述不等式都成立：
∣ a ∣ ≤ n 2 ≤ n − ∣ a ∣ ≤ n + a ≤ n + ∣ a ∣ ≤ 2 ∗ n |a| \le \frac{n}{2} \le n-|a| \le n+a \le n+|a| \le 2*n ∣a∣≤2n≤n−∣a∣≤n+a≤n+∣a∣≤2∗n
即
n 2 ≤ n + a ≤ 2 n \frac{n}{2} \le n+a \le 2n 2n≤n+a≤2n
当 b > 0 时有：
0
<
=
(
1
2
n
)
b
≤
(
n
+
a
)
b
≤
(
2
n
)
b
0
<
=
(
1
2
)
b
n
b
≤
(
n
+
a
)
b
≤
2
b
n
b
\begin{aligned} 0 <= (\frac{1}{2}n)^b \le (n+a)^b \le (2n)^b \\ 0 <= (\frac{1}{2})^bn^b \le (n+a)^b \le 2^bn^b \end{aligned}
0<=(21n)b≤(n+a)b≤(2n)b0<=(21)bnb≤(n+a)b≤2bnb
综上，当 c 1 = ( 1 2 ) b ， c 2 = 2 b c1=(\frac{1}{2})^b，c2=2^b c1=(21)b，c2=2b 时，对所有 n ≥ n 0 = 2 ∣ a ∣ n \ge n_0 = 2|a| n≥n0=2∣a∣，都有 0 ≤ c 1 ∗ n b ≤ ( n + a ) b ≤ c 2 ∗ n b 0 \le c_1*n^b \le (n+a)^b \le c_2*n^b 0≤c1∗nb≤(n+a)b≤c2∗nb，所以 ( n + a ) b = Θ ( n b ) (n+a)^b = \Theta(n^b) (n+a)b=Θ(nb)。
3.1-3
解释“算法A的运行时间至少是 O ( n 2 ) \Omicron(n^2) O(n2)”这一表述是无意义的。
感觉这是个语文题。 O ( g ( n ) ) \Omicron(g(n)) O(g(n)) 表示运行时间的上界，与“至少”用在一起是个病句。就像说插入排序的运行时间至少是 O ( n 2 ) \Omicron(n^2) O(n2)。
作者的解答如下：
3.1-4
2 n + 1 = O ( 2 n ) 2^{n+1} = \Omicron(2^n) 2n+1=O(2n)成立吗？ 2 2 n = O m i c r o n ( 2 n ) 2^{2n} = Omicron(2^n) 22n=Omicron(2n)成立吗？
当 c = 3 时 c = 3 时 c=3时，对于所有 n ≥ n 0 = 1 n \ge n_0 = 1 n≥n0=1，都有 0 ≤ 2 ∗ 2 n = 2 n + 1 ≤ c ∗ 2 n 0 \le 2*2^n = 2^{n+1} \le c*2^n 0≤2∗2n=2n+1≤c∗2n，所以 2 n + 1 = O ( 2 n ) 2^{n+1} = \Omicron(2^n) 2n+1=O(2n)成立。
假设存在 c c c 及 n 0 n_0 n0，使得对所有 n ≥ n 0 n \ge n_0 n≥n0 都有 0 ≤ 2 2 n ≤ c 2 n 0 \le 2^{2n} \le c2^n 0≤22n≤c2n，同除 2 n 2^n 2n得， 0 ≤ 2 n ≤ c 0 \le 2^{n} \le c 0≤2n≤c，因为 c c c 是常量，所以对任意大的 n n n，该不等式不可能成立，故 2 2 n = O m i c r o n ( 2 n ) 2^{2n} = Omicron(2^n) 22n=Omicron(2n)不成立。
3.1-5
证明定理3.1
如果 f ( n ) = Θ ( g ( n ) ) f(n)=\Theta(g(n)) f(n)=Θ(g(n))，则存在正常量 n 0 ， c 1 ， c 2 n_0，c_1，c_2 n0，c1，c2，使得所有 n ≥ n 0 n \ge n_0 n≥n0， 0 ≤ c 1 g ( n ) ≤ f ( n ) ≤ c 2 g ( n ) 0 \le c_1g(n) \le f(n) \le c_2g(n) 0≤c1g(n)≤f(n)≤c2g(n)，根据 Ω ( g ( n ) ) 及 O ( g ( n ) ) \Omega(g(n))及\Omicron(g(n)) Ω(g(n))及O(g(n))的定义不难得出，此时 f ( n ) = Ω ( g ( n ) ) ， f ( n ) = O ( g ( n ) ) f(n)=\Omega(g(n))，f(n)=\Omicron(g(n)) f(n)=Ω(g(n))，f(n)=O(g(n)) 也成立。
如果
f
(
n
)
=
O
(
g
(
n
)
)
f(n)=\Omicron(g(n))
f(n)=O(g(n)) 成立，则存在正常量
n
1
，
c
1
n_1，c_1
n1，c1，使得所有
n
≥
n
1
n \ge n_1
n≥n1，
0
≤
c
1
g
(
n
)
≤
f
(
n
)
0 \le c_1g(n) \le f(n)
0≤c1g(n)≤f(n)。
如果
f
(
n
)
=
Ω
(
g
(
n
)
)
f(n)=\Omega(g(n))
f(n)=Ω(g(n)) 成立，则存在正常量
n
2
，
c
2
n_2，c_2
n2，c2，使得所有
n
≥
n
2
n \ge n_2
n≥n2，
0
≤
f
(
n
)
≤
c
2
g
(
n
)
0 \le f(n) \le c_2g(n)
0≤f(n)≤c2g(n)。
取 n 0 = m a x ( n 1 ， n 2 ) n_0 = max(n_1，n_2) n0=max(n1，n2)，则所有 n ≥ n 0 n \ge n_0 n≥n0， 0 ≤ c 1 g ( n ) ≤ f ( n ) ≤ c 2 g ( n ) 0 \le c_1g(n) \le f(n) \le c_2g(n) 0≤c1g(n)≤f(n)≤c2g(n)
综上， f ( n ) = Ω ( g ( n ) ) ， f ( n ) = O ( g ( n ) ) f(n)=\Omega(g(n))，f(n)=\Omicron(g(n)) f(n)=Ω(g(n))，f(n)=O(g(n)) 是 f ( n ) = Θ ( g ( n ) ) f(n)=\Theta(g(n)) f(n)=Θ(g(n)) 充要条件。
3.1-7
证明 ο ( g ( n ) ) ∩ ω ( g ( n ) ) \omicron(g(n))∩\omega(g(n)) ο(g(n))∩ω(g(n)) 为空。
反证法。
假设 ο ( g ( n ) ) ∩ ω ( g ( n ) ) \omicron(g(n))∩\omega(g(n)) ο(g(n))∩ω(g(n))不为空，则对于任意 c > 0 c \gt 0 c>0，存在 f ( n ) ， n 0 > 0 f(n)，n_0 > 0 f(n)，n0>0，使得对所有 n ≥ n 0 n \ge n_0 n≥n0 都有 0 ≤ f ( n ) < c g ( n ) 0 \le f(n) \lt cg(n) 0≤f(n)<cg(n) 且 0 ≤ c g ( n ) < f ( n ) 0 \le cg(n) \lt f(n) 0≤cg(n)<f(n)，显然不存在这样的f(n)，所以 ο ( g ( n ) ) ∩ ω ( g ( n ) ) \omicron(g(n))∩\omega(g(n)) ο(g(n))∩ω(g(n)) 为空。
3.1-8
给出 Ω ( g ( n , m ) ) ， O ( g ( n , m ) ) \Omega(g(n,m))，\Omicron(g(n,m)) Ω(g(n,m))，O(g(n,m)) 的定义。
3.2-1
因为 f ( n ) f(n) f(n) 和 g ( n ) g(n) g(n) 均为单调递增的函数，则当 x < y x \lt y x<y 时有 f ( x ) ≤ f ( y ) ， g ( x ) ≤ g ( y ) f(x) \le f(y)，g(x) \le g(y) f(x)≤f(y)，g(x)≤g(y)，合并得 f ( x ) + g ( x ) ≤ f ( y ) + g ( y ) f(x)+g(x) \le f(y)+g(y) f(x)+g(x)≤f(y)+g(y)，所以 f ( x ) + g ( y ) f(x)+g(y) f(x)+g(y) 为单调递增函数。
因为 f ( n ) f(n) f(n) 和 g ( n ) g(n) g(n) 均为单调递增的函数，则当 x < y x \lt y x<y时有 g ( x ) ≤ g ( y ) g(x) \le g(y) g(x)≤g(y)， f ( g ( x ) ) ≤ f ( g ( y ) ) f(g(x)) \le f(g(y)) f(g(x))≤f(g(y))，所以 f ( g ( n ) ) f(g(n)) f(g(n)) 是单调递增函数。
因为 f ( n ) f(n) f(n) 和 g ( n ) g(n) g(n) 均为单调递增的函数且非负，则当 x < y x \lt y x<y时有 f ( x ) ∗ g ( x ) ≤ f ( y ) ∗ g ( y ) f(x)*g(x) \le f(y)*g(y) f(x)∗g(x)≤f(y)∗g(y)，所以 f ( x ) ∗ g ( y ) f(x)*g(y) f(x)∗g(y) 为单调递增函数。
3.2-2
证明 a log b c = c log b a a^{\log_{b}{c}} = c^{\log_{b}a} alogbc=clogba
令
a
=
c
n
a=c^n
a=cn，则有
a
log
b
c
=
c
n
log
b
c
=
c
log
b
c
n
=
c
log
b
a
\begin{aligned} a^{\log_{b}{c}} &=c^{n\log_{b}{c}}\\ &=c^{\log_{b}{c^n}} \\ &=c^{\log_{b}{a}} \end{aligned}
alogbc=cnlogbc=clogbcn=clogba
3.2-3
证明 n ! = ο ( n n ) n! = \omicron(n^n) n!=ο(nn)
由 3.20等式 可知，取
n
0
=
1
n_0 = 1
n0=1，对所有
n
≥
n
0
n \ge n_0
n≥n0 有
n
!
=
2
π
n
(
n
e
)
n
e
α
n
\begin{aligned} n! &= \sqrt{2πn}(\frac{n}{e})^ne^{α_n} \\ \end{aligned}
n!=2πn
(en)neαn
因为
1
12
n
+
1
<
α
n
<
1
12
n
\frac{1}{12n+1} < α_n < \frac{1}{12n}
12n+11<αn<12n1，所以有不等式如下：
n
!
=
2
π
n
(
n
e
)
n
e
α
n
n
!
<
2
π
n
(
n
e
)
n
e
n
!
<
2
π
n
e
(
n
n
e
n
)
\begin{aligned} n! &= \sqrt{2πn}(\frac{n}{e})^ne^{α_n} \\ n!&< \sqrt{2πn}(\frac{n}{e})^ne \\ n!&< \sqrt{2πn}e(\frac{n^n}{e^n}) \end{aligned}
n!n!n!=2πn
(en)neαn<2πn
(en)ne<2πn
e(ennn)
设
c
>
0
c>0
c>0，若
2
π
n
e
(
n
n
e
n
)
<
c
n
n
\sqrt{2πn}e(\frac{n^n}{e^n}) < cn^n
2πn
e(ennn)<cnn，则有
2
π
n
e
(
n
n
e
n
)
<
c
n
n
2
π
n
e
(
n
n
e
n
)
<
c
n
n
n
2
π
e
e
n
<
c
2
π
e
c
<
e
n
ln
2
π
e
c
<
ln
e
n
ln
2
π
+
1
−
ln
c
<
n
\begin{aligned} \sqrt{2πn}e(\frac{n^n}{e^n}) &< cn^n \\ \sqrt{2πn}e(\frac{n^n}{e^n}) &< cn^n\sqrt n \\ \frac{\sqrt{2π}e}{e^n} &< c \\ \frac{\sqrt{2π}e}{c} &< e^n \\ \ln {\frac{\sqrt{2π}e}{c}} &< \ln{e^n} \\ \ln {\sqrt{2π}} + 1 - \ln c &< n \end{aligned}
2πn
e(ennn)2πn
e(ennn)en2π
ec2π
elnc2π
eln2π
+1−lnc<cnn<cnnn
<c<en<lnen<n
综上，对于任意
c
>
0
c > 0
c>0，存在
n
0
=
m
a
x
(
1
,
⌈
ln
2
π
+
2
−
ln
c
⌉
)
n_0 = max(1, \lceil {\ln {\sqrt{2π}} + 2 - \ln c} \rceil)
n0=max(1,⌈ln2π
+2−lnc⌉)，对于所有
n
>
=
n
0
n >= n_0
n>=n0 有
0
<
c
n
!
≤
n
n
0 < cn! \le n^n
0<cn!≤nn。
所以 n ! = ο ( n n ) n! = \omicron(n^n) n!=ο(nn)。
n ! = ω ( 2 n ) n! = \omega(2^n) n!=ω(2n)
取 n 0 = 7 n_0 = 7 n0=7 ，对所有 n ≥ n 0 n \ge n_0 n≥n0 有 n ! > 3 n > 2 n n! > 3^n > 2^n n!>3n>2n。
对任意
c
>
0
c > 0
c>0 有，设
c
2
n
<
3
n
c2^n < 3^n
c2n<3n，则有
c
2
n
<
3
n
ln
c
<
l
n
(
3
2
)
n
ln
(
c
−
3
2
)
<
n
\begin{aligned} c2^n &< 3^n \\ \ln c &< ln {(\frac{3}{2})^n} \\ \ln (c - \frac{3}{2}) &< n \end{aligned}
c2nlncln(c−23)<3n<ln(23)n<n
对任意 c > 0 c> 0 c>0，存在 n 0 = m a x ( 7 , ⌈ ln ( c − 3 2 ) ⌉ ) n_0 = max(7, \lceil \ln (c - \frac{3}{2}) \rceil) n0=max(7,⌈ln(c−23)⌉)，对所有 n ≥ n 0 n \ge n_0 n≥n0 有 0 < c ∗ 2 n < n ! 0 \lt c*2^n < n! 0<c∗2n<n!，即 n ! = ω ( 2 n ) n! = \omega(2^n) n!=ω(2n)。
lg ( n ! ) = Θ ( n ∗ lg n ) \lg(n!) = \Theta(n*\lg n) lg(n!)=Θ(n∗lgn)
由 3.20等式 可知，取
n
0
=
1
n_0 = 1
n0=1，对所有
n
≥
n
0
n \ge n_0
n≥n0 有
n
!
=
2
π
n
(
n
e
)
n
e
α
n
\begin{aligned} n! &= \sqrt{2πn}(\frac{n}{e})^ne^{α_n} \\ \end{aligned}
n!=2πn
(en)neαn
有上述等式得：
lg
(
n
!
)
=
lg
(
2
π
n
(
n
e
)
n
e
α
n
)
lg
(
n
!
)
=
lg
(
2
π
n
)
+
n
lg
(
n
)
−
n
lg
(
e
)
+
lg
(
e
α
n
)
lg
(
n
!
)
>
n
lg
(
n
)
−
n
lg
(
e
)
lg
(
n
!
)
>
n
lg
(
n
)
−
n
2
lg
(
e
2
)
\begin{aligned} \lg (n!) &= \lg (\sqrt{2πn}(\frac{n}{e})^ne^{α_n}) \\ \lg (n!) &= \lg (\sqrt{2πn}) + n\lg(n) - n\lg(e) + \lg(e^{α_n}) \\ \lg (n!) &> n\lg(n) - n\lg(e) \\ \lg (n!) &> n\lg(n) - \frac{n}{2}\lg(e^2) \end{aligned}
lg(n!)lg(n!)lg(n!)lg(n!)=lg(2πn
(en)neαn)=lg(2πn
)+nlg(n)−nlg(e)+lg(eαn)>nlg(n)−nlg(e)>nlg(n)−2nlg(e2)
取
n
0
=
⌈
e
2
⌉
n_0 = \lceil e^2 \rceil
n0=⌈e2⌉，对所有
n
≥
n
0
n \ge n_0
n≥n0 都有，
lg
(
n
!
)
>
n
lg
(
n
)
−
n
2
lg
(
e
2
)
lg
(
n
!
)
>
n
lg
(
n
)
−
n
2
lg
(
n
)
lg
(
n
!
)
>
1
2
n
lg
(
n
)
\begin{aligned} \lg (n!) &> n\lg(n) - \frac{n}{2}\lg(e^2) \\ \lg (n!) &> n\lg(n) - \frac{n}{2}\lg(n) \\ \lg (n!) &> \frac{1}{2}n\lg(n) \end{aligned}
lg(n!)lg(n!)lg(n!)>nlg(n)−2nlg(e2)>nlg(n)−2nlg(n)>21nlg(n)
综上，取 n 0 = ⌈ e 2 ⌉ , c 1 = 1 2 n_0 = \lceil e^2 \rceil, c_1 = \frac{1}{2} n0=⌈e2⌉,c1=21，对所有 n ≥ n 0 n \ge n_0 n≥n0 都有， lg ( n ! ) ≥ c 1 n lg ( n ) \lg (n!) \ge c_1n\lg(n) lg(n!)≥c1nlg(n)
令，取
n
0
=
1
n_0 = 1
n0=1，对所有
n
≥
n
0
n \ge n_0
n≥n0 都有
lg
(
n
!
)
=
lg
1
+
lg
2
+
.
.
+
lg
n
<
=
n
lg
n
\begin{aligned} \lg(n!) &= \lg 1 + \lg 2 + .. + \lg n \\ &<= n \lg n \end{aligned}
lg(n!)=lg1+lg2+..+lgn<=nlgn
综上，取 n 0 = m a x ( ⌈ e 2 ⌉ , 1 ) ， c 1 = 1 2 , c 2 = 1 n_0 = max( \lceil e^2 \rceil, 1)，c_1 = \frac{1}{2}, c_2 = 1 n0=max(⌈e2⌉,1)，c1=21,c2=1，对所有 n ≥ n 0 n \ge n_0 n≥n0 都有
0 ≤ c 1 lg ( n lg n ) ≤ lg ( n ! ) ≤ c 2 lg ( n lg n ) 0 \le c_1\lg (n\lg n) \le \lg (n!) \le c_2\lg(n\lg n) 0≤c1lg(nlgn)≤lg(n!)≤c2lg(nlgn)
即 lg ( n ! ) = Θ ( n ∗ lg n ) \lg(n!) = \Theta(n*\lg n) lg(n!)=Θ(n∗lgn)
3.2-4
函数
⌈
lg
n
⌉
!
\lceil\lg n\rceil !
⌈lgn⌉! 和
⌈
lg
lg
n
⌉
!
\lceil \lg \lg n\rceil !
⌈lglgn⌉! 多项式有界吗？
3.2-5
lg ( lg ∗ n ) \lg(\lg^*n) lg(lg∗n) 和 lg ∗ ( lg n ) \lg ^*(\lg n) lg∗(lgn) 哪个渐进更大些？
lg ∗ n \lg^*n lg∗n 的含义就是从 n 开始最少需要多少次运算可以得到一个不超过1的值，那么可得到 lg ∗ ( lg n ) = lg ∗ n − 1 \lg ^*(\lg n) = \lg^*n - 1 lg∗(lgn)=lg∗n−1。
lg ( lg ∗ n ) \lg(\lg^*n) lg(lg∗n) 和 lg ∗ n − 1 \lg^*n - 1 lg∗n−1 相比，显然后者渐进更大些。
3.2-7
当 n = 0 , 1 n = 0 ,1 n=0,1 时易得：
- F 0 = 0 = ϕ 0 − ϕ ^ 0 5 F_0 = 0 = \frac{\phi ^0 - \widehat{\phi}^0}{\sqrt5} F0=0=5 ϕ0−ϕ 0
- F 1 = 1 = ϕ 1 − ϕ ^ 1 5 F_1 = 1 = \frac{\phi ^1 - \widehat{\phi}^1}{\sqrt5} F1=1=5 ϕ1−ϕ 1
设当 n ≥ 2 n \ge 2 n≥2时， F n − 2 = ϕ n − 2 − ϕ ^ n − 2 5 ， F n − 1 = ϕ n − 1 − ϕ ^ n − 1 5 F_{n-2} = \frac{\phi ^{n-2} - \widehat{\phi}^{n-2}}{\sqrt5}，F_{n-1} = \frac{\phi ^{n-1} - \widehat{\phi}^{n-1}}{\sqrt5} Fn−2=5 ϕn−2−ϕ n−2，Fn−1=5 ϕn−1−ϕ n−1 成立，
F n = F n − 1 + F n − 2 = ϕ n − 2 − ϕ ^ n − 2 5 + ϕ n − 1 − ϕ ^ n − 1 5 = ( ϕ n − 2 ( 1 + ϕ ) + ϕ ^ n − 2 ( 1 + ϕ ^ ) ) ∗ 1 5 = ϕ n − ϕ ^ n 5 / / 由 练 习 题 3.2 − 6 可 证 \begin{aligned} F_n &= F_{n-1} + F_{n-2} \\ &= \frac{\phi ^{n-2} - \widehat{\phi}^{n-2}}{\sqrt5} + \frac{\phi ^{n-1} - \widehat{\phi}^{n-1}}{\sqrt5} \\ &= (\phi ^{n-2}(1+\phi) +\widehat{\phi}^{n-2}(1+\widehat{\phi}))*\frac{1}{\sqrt5}\\ &= \frac{\phi ^n - \widehat{\phi}^n}{\sqrt5} // 由练习题3.2-6 可证 \end{aligned} Fn=Fn−1+Fn−2=5 ϕn−2−ϕ n−2+5 ϕn−1−ϕ n−1=(ϕn−2(1+ϕ)+ϕ n−2(1+ϕ ))∗5 1=5 ϕn−ϕ n//由练习题3.2−6可证
3.2-8
证明 k ln k = Θ ( n ) k\ln k = \Theta(n) klnk=Θ(n) 蕴含着 k = Θ ( n / ln n ) k=\Theta(n/\ln n) k=Θ(n/lnn)
由 k ln k = Θ ( n ) k\ln k = \Theta(n) klnk=Θ(n) 可知，存在 $n_0 > 0，c_1 > 0，c_2 > 0 $，使得所有 n ≥ n 0 n \ge n_0 n≥n0 都有:
c 1 n ≤ k ln k ≤ c 2 n c_1n \le k\ln k \le c_2n c1n≤klnk≤c2n
上式三部分同除 ln n \ln n lnn 可得：
c 1 n ln n ≤ k ln k ln n ≤ c 2 n ln n c_1\frac{n}{\ln n} \le k\frac{\ln k}{\ln n} \le c_2\frac{n}{\ln n} c1lnnn≤klnnlnk≤c2lnnn
接下来，尝试证明 ln k ln n \frac{\ln k}{\ln n} lnnlnk 的取值范围。
c
1
n
≤
k
ln
k
ln
c
1
+
ln
n
≤
ln
k
+
ln
ln
k
ln
c
1
+
ln
n
≤
2
ln
k
ln
c
1
ln
n
+
1
≤
2
ln
k
ln
n
ln
c
1
2
ln
n
+
1
2
≤
ln
k
ln
n
1
2
≤
ln
k
ln
n
\begin{aligned} c_1n &\le k \ln k \\ \ln c_1 + \ln n&\le \ln k + \ln \ln k \\ \ln c_1 + \ln n&\le 2\ln k\\ \frac{\ln c_1}{\ln n} + 1 &\le 2\frac{\ln k}{\ln n} \\ \frac{\ln c_1}{2\ln n} + \frac{1}{2} &\le \frac{\ln k}{\ln n} \\ \frac{1}{2} &\le \frac{\ln k}{\ln n} \\ \end{aligned}
c1nlnc1+lnnlnc1+lnnlnnlnc1+12lnnlnc1+2121≤klnk≤lnk+lnlnk≤2lnk≤2lnnlnk≤lnnlnk≤lnnlnk
另外，取
n
0
=
m
a
x
(
n
0
,
c
2
)
n_0 = max(n_0, c_2)
n0=max(n0,c2)，对所有
n
≥
n
0
n \ge n_0
n≥n0 有
c
2
n
≥
k
ln
k
ln
c
2
+
ln
n
≥
ln
k
+
ln
ln
k
ln
c
2
ln
n
+
1
≥
ln
k
ln
n
2
≥
ln
k
ln
n
\begin{aligned} c_2n &\ge k \ln k \\ \ln c_2 + \ln n &\ge \ln k + \ln \ln k \\ \frac{\ln c_2}{\ln n} + 1 &\ge \frac{\ln k}{\ln n} \\ 2 &\ge \frac{\ln k}{\ln n} \end{aligned}
c2nlnc2+lnnlnnlnc2+12≥klnk≥lnk+lnlnk≥lnnlnk≥lnnlnk
综上，由
k ln k ln n ≤ c 2 n ln n k\frac{\ln k}{\ln n} \le c_2\frac{n}{\ln n} klnnlnk≤c2lnnn， 1 2 ≤ ln k ln n \frac{1}{2} \le \frac{\ln k}{\ln n} 21≤lnnlnk
可得：
k ≤ 2 c 2 n ln n k \le {2}{c_2}\frac{n}{\ln n} k≤2c2lnnn
由
c 1 n ln n ≤ k ln k ln n c_1\frac{n}{\ln n} \le k\frac{\ln k}{\ln n} c1lnnn≤klnnlnk， ln k ln n ≤ 2 \frac{\ln k}{\ln n} \le 2 lnnlnk≤2
可得：
c 1 2 n ln n ≤ k \frac{c_1}{2}\frac{n}{\ln n} \le k 2c1lnnn≤k
因此 k ln k = Θ ( n ) k\ln k = \Theta(n) klnk=Θ(n) 蕴含着 k = Θ ( n / ln n ) k=\Theta(n/\ln n) k=Θ(n/lnn)。
思考题 3-1
若 k ≥ d k \ge d k≥d，则 p ( n ) = O ( n k ) p(n) = \Omicron(n^k) p(n)=O(nk)
令 n 0 = 1 ， c 2 = ⌈ ∣ a 0 ∣ + ∣ a 1 ∣ + . . + ∣ a d ∣ ⌉ n_0 = 1，c_2 = \lceil|a_0|+|a_1|+..+|a_d|\rceil n0=1，c2=⌈∣a0∣+∣a1∣+..+∣ad∣⌉，则对于任意 n ≥ n 0 n \ge n_0 n≥n0 都有：
c 2 n k ≥ c 2 n d ≥ ∣ a 0 ∣ n d + ∣ a 1 ∣ n d + . . . + ∣ a d ∣ n d ≥ a 0 n 0 + a 1 n 1 + . . . + a d n d = p ( n ) \begin{aligned} c_2n^k &\ge c_2n^d \\ &\ge |a_0|n^d + |a_1|n^d + ... + |a_d|n^d \\ &\ge a_0n^0 + a_1n^1 + ... + a_dn^d = p(n) \\ \end{aligned} c2nk≥c2nd≥∣a0∣nd+∣a1∣nd+...+∣ad∣nd≥a0n0+a1n1+...+adnd=p(n)
所以，若 k ≥ d k \ge d k≥d，则 p ( n ) = O ( n k ) p(n) = \Omicron(n^k) p(n)=O(nk)
若 k ≤ d k \le d k≤d，则 p ( n ) = Ω ( n k ) p(n) = \Omega(n^k) p(n)=Ω(nk)
设 S 为
p
(
n
)
p(n)
p(n) 中所有小于 0 的系数的累加和的绝对值，则有：
p
(
n
)
=
∑
i
=
0
d
a
i
n
i
≥
a
d
n
d
−
S
n
d
−
1
\begin{aligned} p(n) &= \sum_{i=0}^{d}a_in^i \\ &\ge a_dn^d - Sn^{d-1} \end{aligned}
p(n)=i=0∑daini≥adnd−Snd−1
若要满足 a d n d − S n d − 1 > 0 a_dn^d - Sn^{d-1} > 0 adnd−Snd−1>0，则有：
a d n > S n > S a d \begin{aligned} a_dn &> S \\ n &> \frac{S}{a_d} \end{aligned} adnn>S>adS
取 n 0 = ⌈ S a d ⌉ + 1 n_0 = \lceil \frac{S}{a_d}\rceil + 1 n0=⌈adS⌉+1，存在 c 1 ∈ ( 0 , a d − S n 0 ] c_1∈(0, a_d-\frac{S}{n_0}] c1∈(0,ad−n0S]，满足对所有 n ≥ n 0 n \ge n_0 n≥n0都有：
0 ≤ c 1 ∗ k n k ≤ p ( n ) 0 \le c_1*kn^k \le p(n) 0≤c1∗knk≤p(n)
所以，若 k ≤ d k \le d k≤d，则 p ( n ) = Ω ( n k ) p(n) = \Omega(n^k) p(n)=Ω(nk)。
若 k = d k = d k=d，则 p ( n ) = Θ ( n k ) p(n) = \Theta(n^k) p(n)=Θ(nk)
由上两问可知，当 k = d k = d k=d 时有 p ( n ) = Ω ( n k ) p(n) = \Omega(n^k) p(n)=Ω(nk)， p ( n ) = O ( n k ) p(n) = \Omicron(n^k) p(n)=O(nk)，所以 若 k = d k = d k=d，则 p ( n ) = Θ ( n k ) p(n) = \Theta(n^k) p(n)=Θ(nk)。
若 k > d k > d k>d，则 p ( n ) = ο ( n k ) p(n) = \omicron(n^k) p(n)=ο(nk)。
设 S 为 P ( n ) P(n) P(n) 中所有大于 0 的系数的累加和，则有：
p ( n ) = ∑ i = 0 d a i n i ≤ S n d \begin{aligned} p(n) &= \sum_{i=0}^{d}a_in^i \\ &\le Sn^d \end{aligned} p(n)=i=0∑daini≤Snd
设 c > 0 c > 0 c>0，若要 c n k > p ( n ) cn^k > p(n) cnk>p(n)，则只需 c n k > S n d cn^k > Sn^d cnk>Snd，取 n 0 = ⌈ S c ⌉ + 1 n_0 = \lceil\frac{S}{c}\rceil+1 n0=⌈cS⌉+1，则对于任意 n ≥ n 0 n \ge n_0 n≥n0 都有 c n k > p ( n ) cn^k > p(n) cnk>p(n)。
若 k < d k < d k<d，则 p ( n ) = ω ( n k ) p(n) = \omega(n^k) p(n)=ω(nk)。
设 S 为
p
(
n
)
p(n)
p(n) 中所有小于 0 的系数的累加和的绝对值，则有：
p
(
n
)
=
∑
i
=
0
d
a
i
n
i
≥
a
d
n
d
−
S
n
d
−
1
\begin{aligned} p(n) &= \sum_{i=0}^{d}a_in^i \\ &\ge a_dn^d - Sn^{d-1} \end{aligned}
p(n)=i=0∑daini≥adnd−Snd−1
设 c > 0 c > 0 c>0，若要 p ( n ) > c n k p(n) > cn^k p(n)>cnk，则只需 a d n d − S n d − 1 > c n k a_dn^d - Sn^{d-1} > cn^k adnd−Snd−1>cnk
令 n 0 = ⌈ c + S a d ⌈ + 1 n_0 = \lceil\frac{c+S}{a_d}\lceil + 1 n0=⌈adc+S⌈+1，则对于任意 n ≥ n 0 n \ge n_0 n≥n0都有 p ( n ) > c n k > 0 p(n) > cn^k > 0 p(n)>cnk>0
所以若 k < d k < d k<d，则 p ( n ) = ω ( n k ) p(n) = \omega(n^k) p(n)=ω(nk)
思考题 3-2
|A|B |
O
\Omicron
O|
ο
\omicron
ο|
Ω
\Omega
Ω|
ω
\omega
ω|
Θ
\Theta
Θ|
|–|--|–|--|–|--|–|
|
l
g
k
n
lg^kn
lgkn |
n
ϵ
n^\epsilon
nϵ|N|N|Y|Y|N|
|
n
k
n^k
nk|
c
n
c^n
cn|N|N|Y|Y|N|
|
n
\sqrt n
n
|
n
sin
n
n^{\sin n}
nsinn|N|N|N|N|N|
|
2
n
2^n
2n|
2
n
/
2
2^{n/2}
2n/2|Y|Y|N|N|N|
|
n
lg
c
n^{\lg c}
nlgc|
c
lg
n
c^{\lg n}
clgn|N|N|Y|Y|N|
|
lg
(
n
!
)
\lg (n!)
lg(n!)|
lg
(
n
n
)
\lg (n^n)
lg(nn)|N|N|Y|Y|N|
思考题 3-3
已排序，若 A 在 B 的上面，则代表
A
=
Ω
(
B
)
A = \Omega(B)
A=Ω(B)。
思考题 3-4
f ( n ) = O ( g ( n ) ) f(n) = \Omicron(g(n)) f(n)=O(g(n)) 蕴涵 g ( n ) = O ( f ( n ) ) g(n) = \Omicron(f(n)) g(n)=O(f(n))。
显然不成立，比如 f ( n ) = n 2 ， g ( n ) = n 3 f(n) = n^2，g(n) = n^3 f(n)=n2，g(n)=n3。
f ( n ) + g ( n ) = θ ( f ( n ) + g ( n ) ) f(n) + g(n) = \theta(f(n) + g(n)) f(n)+g(n)=θ(f(n)+g(n))
显然不成立，比如 f ( n ) = 0.1 ， g ( n ) = n 2 f(n) = 0.1，g(n) = n^2 f(n)=0.1，g(n)=n2。
f ( n ) = O ( f ( n ) 2 ) f(n) = \Omicron(f(n)^2) f(n)=O(f(n)2)
不成立，比如 f ( n ) = 1 n f(n) = \frac{1}{n} f(n)=n1
f ( n ) = O ( g ( n ) ) f(n) = \Omicron(g(n)) f(n)=O(g(n)) 蕴涵 g ( n ) = Ω ( f ( n ) ) g(n) = \Omega(f(n)) g(n)=Ω(f(n))。
成立。
因为 f ( n ) = O ( g ( n ) ) f(n) = \Omicron(g(n)) f(n)=O(g(n))，所以存在正数 n 0 , c n_0, c n0,c，满足对所有 n ≥ n 0 n \ge n_0 n≥n0 都有 0 < f ( n ) ≤ c g ( n ) 0 < f(n) \le cg(n) 0<f(n)≤cg(n)。
令 c 1 = 1 c c_1 = \frac{1}{c} c1=c1，则对所有 n ≥ n 0 n \ge n_0 n≥n0 都有 0 < c 1 f ( n ) ≤ g ( n ) 0 < c_1f(n) \le g(n) 0<c1f(n)≤g(n)，即 g ( n ) = Ω ( f ( n ) ) g(n) = \Omega(f(n)) g(n)=Ω(f(n))
f ( n ) = Θ ( f ( n / 2 ) ) f(n) = \Theta(f(n/2)) f(n)=Θ(f(n/2))
不成立，比如这种奇葩函数
r a t e = { 2 n + 2 , n % 2 = 0 1 , n % 2 = 1 rate = \left\{ \begin{array}{l} 2^{n+2}&,n\%2=0 \\ 1&,n\%2=1\\ \end{array}\right. rate={2n+21,n%2=0,n%2=1
f ( n ) + ο ( f ( n ) ) = Θ ( f ( n ) ) f(n) + \omicron(f(n)) = \Theta(f(n)) f(n)+ο(f(n))=Θ(f(n))
对任意
c
>
0
c > 0
c>0，存在
n
0
>
0
n_0 > 0
n0>0，对任意
n
≥
n
0
n \ge n_0
n≥n0，都有
0
<
f
(
n
)
+
ο
(
f
(
n
)
)
<
(
c
+
1
)
f
(
n
)
0 \lt f(n) + \omicron(f(n)) \lt (c+1)f(n)
0<f(n)+ο(f(n))<(c+1)f(n)
令 c 1 = 1 2 ， c 2 = c + 1 c_1 = \frac{1}{2}， c_2 = c+1 c1=21，c2=c+1，则对任意 n ≥ n 0 n \ge n_0 n≥n0，都有
c 1 f ( n ) ≤ f ( n ) + ο ( f ( n ) ) ≤ c 2 f ( n ) c_1f(n) \le f(n) + \omicron(f(n)) \le c_2f(n) c1f(n)≤f(n)+ο(f(n))≤c2f(n)
所以， f ( n ) + ο ( f ( n ) ) = Θ ( f ( n ) ) f(n) + \omicron(f(n)) = \Theta(f(n)) f(n)+ο(f(n))=Θ(f(n))