首页 / 算法 / 《算法导论》第三章函数的增长
《算法导论》第三章函数的增长
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《算法导论》第三章函数的增长，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含18465字，纯文字阅读大概需要27分钟。
内容图文
目录
第三章 函数的增长
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≤c1?g(n)≤f(n)≤c2?g(n)。
举个例子，当分析插入排序的最坏运行时间时：
- f ( n ) = a 2 n 2 + b n + c f(n) =\frac{a}{2}n^2 + bn +c f(n)=2a?n2+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<=(21?n)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≤c1?g(n)≤f(n)≤c2?g(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≤c1?g(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)≤c2?g(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≤c1?g(n)≤f(n)≤c2?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 ) = Θ ( 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} alogb?c=clogb?a
令
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}
alogb?c?=cnlogb?c=clogb?cn=clogb?a?
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π
?e?c2π
?e?lnc2π
?e?ln2π
?+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)?2n?lg(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)?2n?lg(e2)>nlg(n)?2n?lg(n)>21?nlg(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!)≥c1?nlg(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≤c1?lg(nlgn)≤lg(n!)≤c2?lg(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 c1?n≤klnk≤c2?n
上式三部分同除 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} c1?lnnn?≤klnnlnk?≤c2?lnnn?
接下来，尝试证明 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}
c1?nlnc1?+lnnlnc1?+lnnlnnlnc1??+12lnnlnc1??+21?21??≤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}
c2?nlnc2?+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?≤c2?lnnn?， 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≤2c2?lnnn?
由
c 1 n ln ? n ≤ k ln ? k ln ? n c_1\frac{n}{\ln n} \le k\frac{\ln k}{\ln n} c1?lnnn?≤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 2c1??lnnn?≤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} c2?nk?≥c2?nd≥∣a0?∣nd+∣a1?∣nd+...+∣ad?∣nd≥a0?n0+a1?n1+...+ad?nd=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∑d?ai?ni≥ad?nd?Snd?1?
若要满足 a d n d ? S n d ? 1 > 0 a_dn^d - Sn^{d-1} > 0 ad?nd?Snd?1>0，则有：
a d n > S n > S a d \begin{aligned} a_dn &> S \\ n &> \frac{S}{a_d} \end{aligned} ad?nn?>S>ad?S??
取 n 0 = ? S a d ? + 1 n_0 = \lceil \frac{S}{a_d}\rceil + 1 n0?=?ad?S??+1，存在 c 1 ∈ ( 0 , a d ? S n 0 ] c_1∈(0, a_d-\frac{S}{n_0}] c1?∈(0,ad??n0?S?]，满足对所有 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∑d?ai?ni≤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∑d?ai?ni≥ad?nd?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 ad?nd?Snd?1>cnk
令 n 0 = ? c + S a d ? + 1 n_0 = \lceil\frac{c+S}{a_d}\lceil + 1 n0?=?ad?c+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<c1?f(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) c1?f(n)≤f(n)+ο(f(n))≤c2?f(n)
所以， f ( n ) + ο ( f ( n ) ) = Θ ( f ( n ) ) f(n) + \omicron(f(n)) = \Theta(f(n)) f(n)+ο(f(n))=Θ(f(n))
内容总结
以上是互联网集市为您收集整理的《算法导论》第三章函数的增长全部内容，希望文章能够帮你解决《算法导论》第三章函数的增长所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。