【背景】
在概述（二）中，我们着重介绍了对\( O\)的分析，事实上还有很多关于复杂度的分析，以及重要结论，但眼下无论是工业界或是学界都着重分析\(O \),篇幅有限我们在概述（二）中点到即止，详细的分析法还请查阅《计算机程序设计艺术》，本文针对\( O\)的分析回顾一下中学数学基础，方便今后对时间复杂度进行分析。
【标准记号与常用函数】
单调函数
单调递增：
\(m \leq n \Rightarrow f(m) \leq f(n) \)
单调递减：
\( m \leq n \Rightarrow f(m) \geq f(n)\)
严格单调递增：
\( m < n \Rightarrow f(m) < f(n)\)
严格单调递减：
\( m < n \Rightarrow f(m) > f(n) \)
取整函数
向下取整：
\( \lfloor x \rfloor\)
向上取整：
\(\lceil x \rceil \)
取整函数若干性质
- \( x – 1 < \lfloor x \rfloor \leq x \leq \lceil x \rceil < x + 1\)
- \( \lfloor n / 2 \rfloor + \lceil n / 2 \rceil = n\)
-
对于\( n \geq 0, a,b > 0\)有：
\( \lceil \lceil n / a \rceil / b \rceil = \lceil n / ab \rceil\)
\( \lfloor \lfloor n/a\rfloor / b\rfloor = \lfloor n / ab \rfloor\)
\( \lceil a / b \rceil \ leq (a+(b-1)) / b\)
\( \lfloor a / b \rfloor \geq (a-(b-1)) / b\)
\( f(x) = \lfloor x \rfloor, g(x) = \lceil x \rceil为单调增函数\)
多项式函数
- \( p(n) = a_0 + a_1n + a_2n^2+ \dots + a_dn^d; a_d > 0\)
- \( p(n) = \Theta(n^d)\)
- \( f(n) = O(n^k) \Leftrightarrow f(n)多项式有界\)
- \( f(n) = O(1) f(n) \leq c\)
- \( k \geq d \Rightarrow p(n) = O(n^k)\)
- \( k \leq d \Rightarrow p(n) = \Omega(n^k)\)
- \( k > d \Rightarrow p(n) = o(n^k)\)
- \( k < d \Rightarrow p(n) = \omega(n^k)\)
指数函数
对于正整数\( m,n\)和实数a > 0
- \( a^0 = 1\)
- \( a^1 = a\)
- \( a^{-1} = \frac{1}{a}\)
- \( (a^m)^n = a^{mn}\)
- \( (a^m) ^ m = (a^n)^m\)
- \( a^ma^n = a^{n + m}\)
- \( a > 1 \Rightarrow a^n 为单调递增函数\)
- \(\begin{align} a > 1 \Rightarrow \lim_{n \rightarrow \infty}\frac{n^b}{a^n} = 0 \Rightarrow n^b = o(a^n)\end{align}\)
- \(\begin{align} e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots = \sum_{i=0}^{\infty}\frac{x^i}{i!}\end{align}\)
- \( e^x \geq 1 + x\)
- \( |x| \leq 1 \Rightarrow 1 + x \leq e^x \leq 1+x + x^2\)
- \(\begin{align}\lim_{n \rightarrow \infty }(1+ \frac{x}{n})^n = e^x \end{align}\)
对数函数
- \( \log n = \log_2 n\)
- \( \lg n = \log_{10} n\)
- \( \ln n = \log_e n\)
- \( \log^k n = (\log n)^k\)
- \( \log \log n = \log(\log n)\)
对所有实数\( a>0, b > 0, c> 0,和n\)有：
- \( a = b^{\log_b a}\)
- \( \log_c(ab) = \log_c a + \log_c b\)
- \( \log_b a^n = n \log_b a \)
- \( \log_b a = \frac{log_c a}{log_c b}\)
- \( \log_b (1 /a) = -log_b a\)
- \( \log_b a = \frac{1}{log_a b}\)
- \( a^{log_b c} = c^{log_b a}\)
- \( |x| \leq 1 \Rightarrow \ln(1+x) = x – \frac{x^2}{2} + \frac{x^3}{3} – \frac{x^4}{4}+\frac{x^5}{5} + \cdots + (-1)^{n-1}\frac{x^n}{n} \)
- \( for x > -1, \frac{x}{1+x} \leq \ln(1+x) \leq x\)
- \( \begin{align}for any a > 0, \lim_{n\rightarrow \infty} \frac{\log^b n }{(2^a)^{\log n}} = \lim_{n \rightarrow \infty} \frac{\log^b n}{n ^a} = 0 \Rightarrow \log^b n = o(n^a)\end{align}\)
阶乘函数
\( n! = \begin{cases}1&n = 1\\n(n-1)! & n > 0\end{cases}\)
Stirling's approximation:
\( n! = \sqrt{2\pi n}(\frac{n}{e})^n(1+\Theta(\frac{1}{n}))\)
- \( n! = o(n^n)\)
- \( n! = \omega(2^n)\)
- \( \log(n!) = \Omega(n\log n)\)
- \( n! = \sqrt{2\pi n}(\frac{n}{e})^n e^{\alpha_n}，其中\frac{1}{12n+1} < \alpha_n < \frac{1}{12n}\)
【数列求和公式】
等差数列求和：
\( S_n = \frac{(a_1 + a_n)n}{2} = na_1 + \frac{n(n-1)}{2}d\)
等比数列求和:
\( S_n = \frac{a_1(1-q^n)}{1-q} = \frac{a_1 – a_nq}{1-q} (q\neq 0)\)
【非递归算法复杂性分析】
基础：
(1) for/while循环
循环体内计算时间*循环次数；
(2) 嵌套循环
循环体内计算时间*所有循环次数；
(3) 顺序语句
各语句计算时间相加；
(4) if-else语句
if语句计算时间和else语句计算时间的较大者。
一般步骤：
1. 决定用哪个(或哪些)参数作为算法问题规模的度量
可以从问题的描述中得到。
2. 找出算法中的基本语句
通常是最内层循环的循环体。
3. 检查基本语句的执行次数是否只依赖于问题规模
如果基本语句的执行次数还依赖于其他一些特性，则需要分别研究最好情况、最坏情况和平均情况的效率。
4. 建立基本语句执行次数的求和表达式
计算基本语句执行的次数，建立一个代表算法运行时间的求和表达式。
5. 用渐进符号表示这个求和表达式
计算基本语句执行次数的数量级，用大O符号来描述算法增长率的上限。
例子：
int m = 0, i, j;
for(i = 1; i <= n; i++){
for(j = 2*i; j <=n; j++){
m++;
}
}
解法1：算法的基本操作为:\( m++\)，\( m\)的初值为0， \( m\)的值即为执行次数.由于内循环从\(2*n \sim n \),所以\( i\)的最大值满足\( 2i \leq n\)，即\(i \leq n/2 \):
\(\begin{align}m &= \sum_{i=1}^{n/2} \sum_{j = 2i}^n 1 \\&= \sum_{i=1}^{n/2} (n-2i+1) \\&= n\cdot\frac{n}{2}-2\sum_{i=1}^{n/2} + \frac{n}{2} \\ &=\frac{n^2}{2} – \frac{n}{2}(\frac{n}{2} + 1) + \frac{n}{2} = \frac{n^4}{4}\end{align}\)解法2：\(n\)为偶数, 外循环执行\( n / 2\)次. 外循环\(i=1\)时, 内循环\(j\)从\(2\)变到\(n\), 语句\(m++\)执行\(n-1\)次; \(i=2\)时, 内循环执行\(n-3\)次; ……; \(i=n/2\)时, 内循环执行1次.
故:
\(m = (n-1) + (n-3) + \dots + 3 + 1 = \frac{n^2}{4}\)
即：
\(T(n) = O(n^2)\)
【递归算法复杂性分析】
基础：
对递归算法时间复杂性的分析, 关键是根据递归过程建立递推关系式, 然后求解这个递推关系式》
例1：
int factorial(int n){
if(n == 0) return 1;
return n * factorial(n-1);
}
可得递推式：
\(T(n) = \begin{cases}1 & n=0 \\ T(n-1) + 1 &n>0\end{cases}\)
解之：
\(T(n) = n \)
例2：
void Hanoi(int n, char A, char B, char C){
if(n == 1){
printf("A->C");
}else{
Hanoi(n-1, A, C, B);
printf("A->C");
Hanoi(n-1, B, A, C);
}
}
可得递推式：
\(T(n) = \begin{cases}1 & n =1 \\ 2T(n-1) + 1\end{cases}\)
解之：
\(\begin{align}T(n) &=2T(n-1) + 1\\&=2(2T(n-2) + 1) + 1\\&= 2^2T（n-2）+ (2 + 1) \\&=\dots \\&= 2^{n-1} + 2^{n-2} + \dots + 2^2 + 2 + 1 \\&=2^n -1 \\&=O(2^n)\end{align}\)扩展递归
扩展递归（extended recusion）是一种常用的求解递推关系式的基本技术，扩展就是将递推关系式中等式右边的项根据递推式进行替换，扩展后的项被再次扩展，依次下去，会得到一个求和表达式，然后可以借助求和技术进行求解。
例：求解下述递推式时间复杂性：
\( T(n) = \begin{cases} 7 & n =1 \\ 2T(n /2) + 5n^2 & n > 1\end{cases}\)解：
简单起见：设\( n = 2^k\),将递推式进行扩展：
\(\begin{align}T(n) &= 2T(n/2)+ 5n^5 \\&=2(2T(n/4)+5(n/2)^2) + 5n^2 \\ &= \dots \\ &=2^kT(1) + 2^{k-1} \times 5(frac{n}{2^{k-1}})^2 + \cdots + 2\times5(\frac{n}{2})^2 + 5n^2 \\&=7n + 5\sum_{i=0}^{k-1}(n^2)(2^i) \\&= 7n + 5n^2(2-\frac{1}{2^{k-1}}) \\&= 10n^2 – 3n \\&\leq 10n^2 \\&= O(n^2)\end{align}\)【概述小结】
算法与程序
-
算法基本概念和性质
-
算法描述方法
问题求解过程
算法复杂性分析
-
算法复杂性基本概念
-
算法复杂性的渐近性态
-
算法渐近分析记号的定义和性质
-
非递归算法和递归算法的复杂性分析
【参考文献】
-
2019年广西师范大学计算机与信息工程学院算法设计与分析课件[OL].李志欣教授.2019.01.01
[…] 1、时间复杂度分析 20190201 20190216 20190217 […]