课程链接：https://www.icourse163.org/course/PKU-1002525003
简单说来：
f ( n ) = O ( g ( n ) ) f(n)=\Omicron(g(n)) f(n)=O(g(n)) 即 f ( n ) f(n) f(n) 的阶不高于 g ( n ) g(n) g(n) 的阶
f ( n ) = Ω ( g ( n ) ) f(n)=\Omega(g(n)) f(n)=Ω(g(n)) 即 f ( n ) f(n) f(n) 的阶不低于 g ( n ) g(n) g(n) 的阶
f ( n ) = Θ ( g ( n ) ) f(n)=\Theta(g(n)) f(n)=Θ(g(n)) 即 f ( n ) f(n) f(n) 和 g ( n ) g(n) g(n) 同阶
f ( n ) = ο ( g ( n ) ) f(n)=\omicron(g(n)) f(n)=ο(g(n)) 即 f ( n ) f(n) f(n) 的阶低于 g ( n ) g(n) g(n) 的阶
f ( n ) = ω ( g ( n ) ) f(n)=\omega(g(n)) f(n)=ω(g(n)) 即 f ( n ) f(n) f(n) 的阶高于 g ( n ) g(n) g(n) 的阶
定理1
设 f f f 和 g g g 是定义域为自然数集合的函数，
如果 lim n → ∞ f ( n ) g ( n ) \lim\limits_{n\rightarrow \infty}\frac{f(n)}{g(n)} n→∞limg(n)f(n) 存在，并且等于某个常数 c > 0 c>0 c>0，那么 f ( n ) = Θ ( g ( n ) ) f(n) = \Theta(g(n)) f(n)=Θ(g(n))
如果 lim n → ∞ f ( n ) g ( n ) = 0 \lim\limits_{n\rightarrow\infty}\frac{f(n)}{g(n)} = 0 n→∞limg(n)f(n)=0，那么 f ( n ) = o ( g ( n ) ) f(n) = o(g(n)) f(n)=o(g(n))
如果 lim n → ∞ f ( n ) g ( n ) = + ∞ \lim\limits_{n\rightarrow\infty}\frac{f(n)}{g(n)} =+∞ n→∞limg(n)f(n)=+∞，那么 f ( n ) = ω ( g ( n ) ) f(n) = ω(g(n)) f(n)=ω(g(n))
一些重要结果
可证明：多项式函数的阶低于指数函数的阶 n d = o ( r n ) n^{d} = o(r^{n}) nd=o(rn)， r > 1 r >1 r>1， d > 0 d > 0 d>0
可证明：对数函数的阶低于幂函数的阶 ln n = o ( n d ) \ln n = o (n^d ) lnn=o(nd)， d > 0 d > 0 d>0
定理2：函数的阶之间的关系具有传递性
设函数 f , g , h f,g,h f,g,h 的定义域为自然数集合，
如果 f = O ( g ) f=O(g) f=O(g) 且 g = O ( h ) g=O(h) g=O(h)，那么 f = O ( h ) f=O(h) f=O(h)
如果 f = Ω ( g ) f=Ω(g) f=Ω(g) 且 g = Ω ( h ) g=Ω(h) g=Ω(h)， 那么 f = Ω ( h ) f =Ω (h) f=Ω(h)
如果 f = Θ ( g ) f=Θ(g) f=Θ(g) 和 g = Θ ( h ) g=Θ(h) g=Θ(h)， 那么 f = Θ ( h ) f =Θ (h) f=Θ(h)
定理3
假设函数 f f f 和 g g g 的定义域为自然数集，若对某个其它函数 h h h，有 f = O ( h ) f =O(h) f=O(h) 和 g = O ( h ) g=O(h) g=O(h)，那么 f + g = O ( h ) f + g = O(h) f+g=O(h)。
该性质可以推广到有限个函数。
算法由有限步骤构成，若每一步的时间复杂度函数的上界都是 h ( n ) h(n) h(n)，那么该算法的时间复杂度函数可以写作 O ( h ( n ) ) O(h(n)) O(h(n))。
对数函数
log k n = Θ ( log l n ) \log_kn = Θ (\log_l n) logkn=Θ(logln)
log b n = o ( n α ) α > 0 \log_bn = o(n^α)\ \ \ α > 0 logbn=o(nα) α>0
a log b n = n log b a a^{\log_b n} = n^{\log_b a} alogbn=nlogba
指数函数与阶乘
Stirling公式： n ! = 2 π n ( n e ) n ( 1 + Θ ( 1 n ) ) n!=\sqrt{2 \pi n}(\frac{n}{e})^n(1+\Theta(\frac{1}{n})) n!=2πn (en)n(1+Θ(n1))
n ! = o ( n n ) n! = o(n^n) n!=o(nn)
n ! = ω ( 2 n ) n! = ω (2^n) n!=ω(2n)
log ( n ! ) = Θ ( n log n ) \log(n!) = Θ(n \log n) log(n!)=Θ(nlogn)
取整函数
定义：
⌊ x ⌋ \lfloor x \rfloor ⌊x⌋： 表示小于等于 x x x 的最大的整数
⌈ x ⌉ \lceil x \rceil ⌈x⌉： 表示大于等于 x x x 的最小的整数
性质：
x − 1 < ⌊ x ⌋ ≤ x ≤ ⌈ x ⌉ < x + 1 x−1< \lfloor x \rfloor ≤ x ≤ \lceil x \rceil< x+1 x−1<⌊x⌋≤x≤⌈x⌉<x+1
⌊ x + n ⌋ = ⌊ x ⌋ + n \lfloor x+n \rfloor = \lfloor x \rfloor + n ⌊x+n⌋=⌊x⌋+n， ⌈ x + n ⌉ = ⌈ x ⌉ + n \lceil x+n \rceil = \lceil x \rceil+n ⌈x+n⌉=⌈x⌉+n， n n n 为整数
⌈ n 2 ⌉ + ⌊ n 2 ⌋ = n \lceil \frac{n}{2} \rceil+\lfloor \frac{n}{2} \rfloor=n ⌈2n⌉+⌊2n⌋=n
⌈ ⌈ n a ⌉ b ⌉ = ⌈ n a b ⌉ \lceil \frac{\lceil \frac{n}{a} \rceil}{b} \rceil=\lceil \frac{n}{ab} \rceil ⌈b⌈an⌉⌉=⌈abn⌉， ⌊ ⌊ n a ⌋ b ⌋ = ⌊ n a b ⌋ \lfloor \frac{\lfloor \frac{n}{a} \rfloor}{b} \rfloor=\lfloor \frac{n}{ab} \rfloor ⌊b⌊an⌋⌋=⌊abn⌋
∑ k = 1 n a k = n ( a 1 + a n ) 2 \sum\limits_{k=1}^na_k=\frac{n(a_1+a_n)}{2} k=1∑nak=2n(a1+an)
∑ k = 0 n a q k = a ( 1 − q n + 1 ) 1 − q \sum\limits_{k=0}^naq^k=\frac{a(1-q^{n+1})}{1-q} k=0∑naqk=1−qa(1−qn+1)
∑ k = 0 ∞ a q k = a 1 − q ( q < 1 ) \sum\limits_{k=0}^{\infty}aq^k=\frac{a}{1-q}\ \ (q<1) k=0∑∞aqk=1−qa (q<1)
∑ k = 1 n 1 k = ln n + O ( 1 ) \sum\limits_{k=1}^n\frac{1}{k}=\ln n+O(1) k=1∑nk1=lnn+O(1)
∑ k = 1 n a k ≤ n a m a x \sum\limits_{k=1}^na_k \leq n a_{max} k=1∑nak≤namax
假设存在常数
r
<
1
r <1
r<1，使得对一切
k
≥
0
k \geq 0
k≥0 有
a
k
+
1
/
a
k
≤
r
a_{k+1}/a_k \leq r
ak+1/ak≤r 成立，即有
a
1
≤
a
0
r
，
a
2
≤
a
1
r
≤
a
0
r
2
，
.
.
.
a_1 \leq a_0r，a_2 \leq a_1r \leq a_0r^2，...
a1≤a0r，a2≤a1r≤a0r2，...
则
∑
k
=
0
n
a
k
≤
∑
k
=
0
∞
a
0
r
k
=
a
0
∑
k
=
0
∞
r
k
=
a
0
1
−
r
\sum\limits_{k=0}^na_k \leq \sum\limits_{k=0}^{\infty}a_0r^k=a_0\sum\limits_{k=0}^{\infty}r^k=\frac{a_0}{1-r}
k=0∑nak≤k=0∑∞a0rk=a0k=0∑∞rk=1−ra0
例：估计 ∑ k = 1 n 1 k \sum\limits_{k=1}^n\frac{1}{k} k=1∑nk1 的渐近的界
解：
基本步骤：
不断用递推方程的右部替换左部
每次替换，随着 n n n 的降低在和式中多出一项
直到出现初值停止迭代
将初值代入并对和式求和
可用数学归纳法验证解的正确性
例1：Hanoi塔算法 { T ( n ) = 2 T ( n − 1 ) + 1 T ( 1 ) = 1 \left\{\begin{array}{l}T(n)=2T(n-1)+1 \\ T(1)=1\end{array}\right. {T(n)=2T(n−1)+1T(1)=1
解：
例2：插入排序算法 { W ( n ) = W ( n − 1 ) + n − 1 W ( 1 ) = 0 \left\{\begin{array}{l}W(n)=W(n-1)+n-1 \\ W(1)=0\end{array}\right. {W(n)=W(n−1)+n−1W(1)=0
解：
基本步骤：
将对 n n n 的递推式换成对其他变元 k k k 的递推式
对 k k k 直接迭代
将解 (关于 k k k 的函数) 转换成关于 n n n 的函数
例：二分归并排序递推方程： { W ( n ) = 2 W ( n / 2 ) + n − 1 W ( 1 ) = 0 \left\{\begin{array}{l}W(n)=2W(n/2)+n-1 \\ W(1)=0\end{array}\right. {W(n)=2W(n/2)+n−1W(1)=0
解：
假设 n = 2 k n=2^k n=2k，换元： { W ( 2 k ) = 2 W ( 2 k − 1 ) + 2 k − 1 W ( 0 ) = 0 \left\{\begin{array}{l}W(2^k)=2W(2^{k-1})+2^k-1 \\ W(0)=0\end{array}\right. {W(2k)=2W(2k−1)+2k−1W(0)=0
迭代求解：
证明：递推方程 { W ( n ) = W ( n − 1 ) + n − 1 W ( 1 ) = 0 \left\{\begin{array}{l}W(n)=W(n-1)+n-1 \\ W(1)=0\end{array}\right. {W(n)=W(n−1)+n−1W(1)=0 的解是 W ( n ) = n ( n − 1 ) / 2 W(n)=n(n-1)/2 W(n)=n(n−1)/2
方法：数学归纳法
证： n = 1 n=1 n=1， W ( 1 ) = 1 × ( 1 − 1 ) / 2 = 0 W(1)=1×(1-1)/2 = 0 W(1)=1×(1−1)/2=0
假设对于 n n n，解满足方程，
则 W ( n + 1 ) = W ( n ) + n = n ( n − 1 ) / 2 + n = n [ ( n − 1 ) / 2 + 1 ] = n ( n + 1 ) / 2 W(n+1)= W(n)+n= n(n-1)/2 + n= n[(n-1)/2+1]= n(n+1)/2 W(n+1)=W(n)+n=n(n−1)/2+n=n[(n−1)/2+1]=n(n+1)/2
对于高阶递推方程先要用差消法化简为一阶方程，然后迭代求解。
例：求快速排序平均工作量
解：
有 n n n 种可能的输入，对每个输入，划分的比较次数都是 n − 1 n-1 n−1
工作量 = 子问题工作量 + 划分工作量。故工作量总和如下：
假设首元素排好序在每个位置是等概率的，故快速排序平均工作量为
{ T ( n ) = 2 n ∑ i = 1 n − 1 T ( i ) + O ( n ) ， n ≥ 2 T ( 1 ) = 0 \left\{\begin{array}{l}T(n)=\frac{2}{n}\sum\limits_{i=1}^{n-1}T(i)+O(n)，n \geq 2 \\ T(1)=0\end{array}\right. ⎩ ⎨ ⎧T(n)=n2i=1∑n−1T(i)+O(n)，n≥2T(1)=0
这是一个全部历史的递推方程。对于高阶方程应该先化简，然后迭代。
差消化简：利用两个方程相减，将右边的项尽可能消去，以达到降阶的目的。
迭代求解：
递归树是迭代的图形表述
递归树的生成过程与迭代过程一致
递归树上所有项恰好是迭代之后产生和式中的项
对递归树上的项求和就是迭代后方程的解
如果递归树上某结点标记为 W ( m ) W(m) W(m)， W ( m ) = W ( m 1 ) + . . . + W ( m t ) + f ( m ) + . . . + g ( m ) W(m) = W(m_1)+...+W(m_t)+ f(m)+...+g(m) W(m)=W(m1)+...+W(mt)+f(m)+...+g(m)， m 1 , . . . , m t < m m_1, ... , m_t< m m1,...,mt<m，其中 W ( m 1 ) , . . . , W ( m t ) W(m_1),...,W(m_t) W(m1),...,W(mt) 称为函数项。
初始，递归树只有根结点, 其值为 W ( n ) W(n) W(n)
不断继续下述过程：
将函数项叶结点的迭代式 W ( m ) W(m) W(m) 表示成二层子树
用该子树替换该叶结点
继续递归树的生成，直到树中无函数项 (只有初值) 为止。
例1：二分归并排序 W ( n ) = 2 W ( n / 2 ) + n − 1 W(n)=2W(n/2)+n-1 W(n)=2W(n/2)+n−1
解：
对递归树上的量求和：
W ( n ) = n − 1 + n − 2 + . . . + n − 2 k − 1 = k n − ( 2 k − 1 ) = n log n − n + 1 W(n)=n-1+n-2+...+n-2^{k-1}=kn-(2^k-1)=n\log n-n+1 W(n)=n−1+n−2+...+n−2k−1=kn−(2k−1)=nlogn−n+1
例2：求解方程： T ( n ) = T ( n / 3 ) + T ( 2 n / 3 ) + n T(n)=T(n/3)+T(2n/3)+n T(n)=T(n/3)+T(2n/3)+n
解：
求和：递归树层数 k k k，每层 O ( n ) O(n) O(n)
n ( 2 / 3 ) k = 1 ⇒ ( 3 / 2 ) k = n ⇒ k = O ( l o g 3 / 2 n ) n(2/3)k =1 \Rightarrow (3/2)k = n \Rightarrow k = O(log3/2n) n(2/3)k=1⇒(3/2)k=n⇒k=O(log3/2n)
故 T ( n ) = O ( n l o g n ) T(n)=O(nlogn) T(n)=O(nlogn)
求解递推方程 T ( n ) = a T ( n / b ) + f ( n ) T(n) = a T(n/b) + f(n) T(n)=aT(n/b)+f(n)
a a a：归约后的子问题个数
n / b n/b n/b：归约后子问题的规模
f ( n ) f(n) f(n)：归约过程及组合子问题的解的工作量
主定理
设 a ≥ 1 , b > 1 a \geq1, b>1 a≥1,b>1 为常数， f ( n ) f(n) f(n) 为函数， T ( n ) T(n) T(n) 为非负整数，且 T ( n ) = a T ( n / b ) + f ( n ) T(n)=aT(n/b)+f(n) T(n)=aT(n/b)+f(n)，则
若 f ( n ) = O ( n log b a − ξ ) ， ξ > 0 f(n)=O(n^{\log_ba-\xi})，\xi>0 f(n)=O(nlogba−ξ)，ξ>0，那么 T ( n ) = Θ ( n log b a ) T(n)=\Theta(n^{\log_ba}) T(n)=Θ(nlogba)
若 f ( n ) = Θ ( n log b a ) f(n)=\Theta(n^{\log_ba}) f(n)=Θ(nlogba)，那么 T ( n ) = Θ ( n log b a log n ) T(n)=\Theta(n^{\log_ba} \log n) T(n)=Θ(nlogbalogn)
若 f ( n ) = Ω ( n log b a + ξ ) ， ξ > 0 f(n)=\Omega(n^{\log_ba + \xi})，\xi > 0 f(n)=Ω(nlogba+ξ)，ξ>0，且对于某个常数 c < 1 c<1 c<1 和充分大的 n n n 有 a f ( n / b ) ≤ c f ( n ) af(n/b) \leq cf(n) af(n/b)≤cf(n)，那么 T ( n ) = Θ ( f ( n ) ) T(n)=\Theta(f(n)) T(n)=Θ(f(n))
例1
求解递推方程 T ( n ) = 9 T ( n / 3 ) + n T(n) = 9T(n/3) + n T(n)=9T(n/3)+n
解：
上述递推方程中的 a = 9 ， b = 3 ， f ( n ) = n ， n log 3 9 = n 2 ， f ( n ) = O ( n log 3 9 − 1 ) a = 9，b = 3，f(n) = n，n^{\log_39} = n^2，f(n) = O(n^{\log_39-1}) a=9，b=3，f(n)=n，nlog39=n2，f(n)=O(nlog39−1)
相当于主定理的Case1，其中 ξ = 1 \xi =1 ξ=1，根据定理得到 T ( n ) = Θ ( n 2 ) T(n) = \Theta(n^2) T(n)=Θ(n2)
例2
求解递推方程 T ( n ) = T ( 2 n / 3 ) + 1 T(n) = T(2n/3) + 1 T(n)=T(2n/3)+1
解：
上述递推方程中的 a = 1 ， b = 3 / 2 ， f ( n ) = 1 ， n log 3 / 2 1 = n 0 = 1 a = 1，b = 3/2，f(n) = 1，n^{\log_{3/2}1} = n^0 = 1 a=1，b=3/2，f(n)=1，nlog3/21=n0=1
相当于主定理的Case2，根据定理得到 T ( n ) = Θ ( log n ) T(n) = \Theta( \log n) T(n)=Θ(logn)
例3
求解递推方程 T ( n ) = 3 T ( n / 4 ) + n log n T(n) = 3T(n/4) + n\log n T(n)=3T(n/4)+nlogn
解：
上述递推方程中的 a = 3 ， b = 4 ， f ( n ) = n log n a = 3，b = 4，f(n) = n\log n a=3，b=4，f(n)=nlogn
n log n = Ω ( n log 4 3 + ξ ) ≈ Ω ( n 0.793 + ξ ) n\log n=\Omega( n^{\log_43+ \xi}) \approx \Omega( n^{0.793+\xi}) nlogn=Ω(nlog43+ξ)≈Ω(n0.793+ξ)，取 ξ = 0.2 \xi = 0.2 ξ=0.2 即可。
条件验证：
要使 a f ( n / b ) ≤ c f ( n ) af (n/b) \leq c f (n) af(n/b)≤cf(n) 成立，代入 f ( n ) = n log n f (n) = n \log n f(n)=nlogn，得到 3 ( n / 4 ) log ( n / 4 ) ≤ c n log n 3 (n/4) \log (n/4) \leq cn\log n 3(n/4)log(n/4)≤cnlogn，
所以只要 c ≥ 3 / 4 c \geq 3/4 c≥3/4，上述不等式可以对所有充分大的 n n n 成立。
相当于主定理的Case3，因此有 T ( n ) = Θ ( f ( n ) ) = Θ ( n l o g n ) T(n)=\Theta(f (n))=\Theta(nlogn) T(n)=Θ(f(n))=Θ(nlogn)
例4
求解 T ( n ) = 2 T ( n / 2 ) + n log n T(n)=2T(n/2)+n\log n T(n)=2T(n/2)+nlogn
解：
a = b = 2 ， n log b a = n ， f ( n ) = n log n a=b=2，n^{\log_ba}=n，f(n)=n\log n a=b=2，nlogba=n，f(n)=nlogn
不存在 ξ > 0 \xi >0 ξ>0 使 n log n = Ω ( n 1 + ξ ) n \log n = \Omega( n^{1+\xi}) nlogn=Ω(n1+ξ) 成立
不存在 c < 1 c <1 c<1 使 a f ( n / b ) = 2 ( n / 2 ) log ( n / 2 ) = n ( log n − 1 ) ≤ c f ( n ) = c n log n af(n/b) = 2(n/2)\log(n/2)=n(\log n-1) \leq cf(n) = cn\log n af(n/b)=2(n/2)log(n/2)=n(logn−1)≤cf(n)=cnlogn 对所有充分大的 n n n 成立
递归树求解：
求和：
T ( n ) = n log n + n ( log n − 1 ) + n ( log n − 2 ) + . . . + n ( log n − k + 1 ) = ( n log n ) log n − n ( 1 + 2 + . . . + k − 1 ) = n log 2 n − n k ( k − 1 ) / 2 = O ( n log 2 n ) \begin{aligned} T(n) &=n\log n+n(\log n - 1) + n(\log n-2)+...+n(\log n-k+1)\\ &=(n\log n)\log n-n(1+2+...+k-1)\\ &=n\log^2n-nk(k-1)/2\\ &=O(n\log^2n) \end{aligned} T(n)=nlogn+n(logn−1)+n(logn−2)+...+n(logn−k+1)=(nlogn)logn−n(1+2+...+k−1)=nlog2n−nk(k−1)/2=O(nlog2n)
