176-算法复杂度分析概要.md

一：渐近符号

1.1 符号的辨析

1.1.1 符号$O$

$O$，读作“大O”，非正式来说，$O(g(n))$是增长次数小于等于$g(n)$及其常数倍（$n$趋向于无穷大）的函数集合。

定义 如果函数$f(n)$包含在$O(g(n))$中，记作$f(n)∈O(g(n))$（平时使用为了方便书写，我们通常使用$f(n)=O(g(n))$代替）。它的成立条件是：对于所有足够大的$n$，$f(n)$的上界由$g(n)$的常数倍所确定，也就是说，存在大于$0$的常数$c$和非负整数$n_0$，使得对于所有的$n≥n_0$来说，$f(n)≤c⋅g(n)$。

下图说明了这个定义：

下面给出几个例子：

$$ \begin{align} n&=O(n^2)\tag{1.1.1.1}\\ 100n+5&=O(n^2)\tag{1.1.1.2}\\ \frac 12n(n-1)&=O(n^2)\tag{1.1.1.3}\\ n^3&≠O(n^2)\tag{1.1.1.4}\\ 0.00001n^3&≠O(n^2)\tag{1.1.1.5} \end{align} $$

1.1.2 符号$Ω$

$Ω$，读作“omega”，$Ω(g(n))$是增长次数大于等于$g(n)$及其常数倍（$n$趋向于无穷大）的函数集合。

定义 如果函数$f(n)$包含在$Ω(g(n))$中，记作$f(n)=Ω(g(n))$。它的成立条件是：对于所有足够大的$n$，$f(n)$的下界由$g(n)$的常数倍所确定，也就是说，存在大于$0$的常数$c$和非负整数$n_0$，使得对于所有的$n≥n_0$来说，$f(n)≥c⋅g(n)$。

下图说明了这个定义：

下面给出几个例子：

$$ \begin{align} n^3&=Ω(n^2)\tag{1.1.2.1}\\ \frac 12n(n-1)&=Ω(n^2)\tag{1.1.2.2}\\ 100n+5&≠Ω(n^2)\tag{1.1.2.3} \end{align} $$

1.1.3 符号$Θ$

读作“theta”。

定义 如果函数$f(n)$包含在$Θ(g(n))$中，记作$f(n)=Θ(g(n))$。它的成立条件是：对于所有足够大的$n$，$f(n)$的上界和下界由$g(n)$的常数倍所确定，也就是说，存在大于$0$的常数$c_1,c_2$和非负整数$n_0$，使得对于所有的$n≥n_0$来说，$c_1⋅g(n)≤f(n)≤c_2⋅g(n)$。

下图说明了这个定义：

下面给出几个例子：

$$ \begin{align} \frac 12n(n-1)&=Θ(n^2)\tag{$c_1=\frac 14,c_2=\frac 12,n_0=2$}\\ 6n^3&≠Θ(n^2)\tag{1.1.3.2} \end{align} $$

1.2 符号的性质

定理 如果$t_1(n)=O(g_1(n))$并且$t_2(n)=O(g_2(n))$，则 $$ t_1(n)+t_2(n)=O(\max{g_1(n),g_2(n)}) $$

对于$Ω$和$Θ$符号，同样成立。

证明 增长次数的证明是基于以下简单事实：对于$4$个任意实数$a_1,b_1,a_2,b_2$，如果$a_1≤b_1$并且$a_2≤b_2$，则$a_1+a_2≤2\max{b_1,b_2}$。

因为$t_1(n)=O(g_1(n))$，且存在正常量$c_1$和非负整数$n_1$，使得对于所有的$n≥n_1$,有$t_1(n)≤c_1g_1(n)$。同理，因为$t_2(n)=O(g_2(n))$，对于所有的$n≥n_2$，亦有$t_2(n)≤c_2g_2(n)$。

假设$c_3=\max{c_1,c_2}$并且$n≥\max{n_1,n_2}$，就可以利用两个不等式的结论将其相加，得出以下结论：

$$ \begin{align} t_1(n)+t_2(n)&≤c_1g_1(n)+c_2g_2(n)\tag{1.2.1}\\ &≤c_3g_1(n)+c_3g_2(n)=c_3[g_1(n)+g_2(n)]\tag{1.2.2}\\ &≤c_3⋅2\max{g_1(n),g_2(n)}\tag{1.2.3} \end{align} $$

那么，对于两个连续执行部分组成的算法，应该如何应用这个特性呢？它意味着该算法的整体效率是由具有较大增长次数的部分所决定的，即效率较差的部分决定。

二：复杂度求解方法分析

对于一个普通函数（即非递归函数），其时间复杂度自然易求。下面我们主要谈谈如何求解递归函数的时间复杂度。

递归函数通常会有以下的方程式：

$$ T(n)=aT(\frac nb)+f(n)\tag{2.1} $$ 其中，$a≥1,b>1$，且都是常数，$f(n)$是渐近正函数。递归式$(2.1)$描述的是这样一种算法的运行时间：它将规模为$n$的问题分解为$a$个子问题，每个子问题规模为$\frac nb$，其中$a≥1,b>1$。$a$个子问题递归地求解，每个花费时间$T(\frac nb)$。函数$f(n)$包含了问题分解和子问题解合并的代价。

解决上述方程式常用的方法有两种：主定理和分治法。

2.1 主定理（Master Theorem）

定理 令$a≥1,b>1$，且都是常数，$f(n)$是一个函数，$T(n)$是定义在非负整数上的递归式，即：

$$ T(n)=aT(\frac nb)+f(n) $$

其中我们将$\frac nb​$解释为$⌊\frac nb⌋​$或$⌈\frac nb⌉​$。那么$T(n)​$有如下渐近界：

（Case 1）如果$f(n)=O(n^c)$，其中$c<log_ba$，则：

$$ T(n)=Θ(n^{log_ba}) $$

（Case 2）如果存在常数$k≥0$，使$f(n)=Θ(n^clog^{k}n)$，其中$c=log_ba$，则：

$$ T(n)=Θ(n^clog^{k+1}n) $$

（Case 3）如果$f(n)=Ω(n^c)$，其中$c>log_ba$，并且对某个常数$k<1$和所有足够大的$n$有$af(\frac nb)≤kf(n)$，则：

$$ T(n)=Θ(f(n)) $$

算法导论已有关于这个定理的证明，故此处省略，有兴趣的读者可以去翻阅下。

2.2 分治法

分治法先把给定的实例划分为若干个较小的实例，对每个实例递归求解，然后如果有必要，再把较小实例的解合并成给定实例的一个解。假设所有较小实例的规模都为$\frac nb$，其中$a$个实例需要实际求解，对于$n=b^k,k=1,2,3...$，其中$a≥1,b>1$，得到以下结果：

$$ \begin{align} T(n)&=aT(\frac nb)+f(n)\tag{原始递归方程式}\\ T(b^k)&=aT(b^{k-1})+f(b^k)\tag{2.2.2}\\ &=a[aT(b^{k-2})+f(b^{k-1})]+f(b^k)=a^2T(b^{k-2})+af(b^{k-1})+f(b^k)\tag{2.2.3}\\ &=a^3T(b^{k-3})+a^2f(b^{k-2})+af(b^{k-1})+f(b^k)\tag{2.2.4}\\ &=...\tag{2.2.5}\\ &=a^kT(1)+a^{k-1}f(b^1)+a^{k-2}f(b^2)+...+a^0f(b^k)\tag{2.2.6}\\ &=a^k[T(1)+\sum_{j=1}^{k} {\frac {f(b^j)}{a^j}}]\tag{2.2.7} \end{align} $$

由于$a^k=a^{log_bn}=n^{log_ba}$,当$n=b^k$时，对于式$(2.2.7)$我们可以推出下式：

$$ T(n)=n^{log_ba}[T(1)+\sum_{j=1}^{log_bn}{\frac {f(b^j)}{a^j}}]\tag{2.2.8} $$

显然，$T(n)$的增长次数取决于常数$a$和$b$的值以及函数$f(n)$的增长次数。

三：无意发现的定理

以下是我自己在演算时无意发现的两条定理，并给出了证明。该定理依旧建立在递归方程式中，即：

$$ T(n)=aT(\frac nb)+f(n)\tag{$a≥1,b>1$} $$

根据以上的方程式有以下两个定理：

3.1 定理1

定理1 对于递归方程式，若$a=1,b>1,f(n)=c,c$为某个常数，即：

$$ T(n)=T(\frac nb)+c $$

则：

$$ T(n)=Θ(logn) $$

证明 应用主定理 Case 2，其中$c=log_ba=log_b1=0$，再使$k=0$，则$f(n)=Θ(n^clog^kn)=Θ(1)$，这里的$f(n)$即等于常数$c$，证明成立。

3.2 定理2

定理2 对于递归方程式，若$a=1,b>1,f(n)=kn+p$，其中$k>0,p>0$且为某个常数（也就是$f(n)$是一个线性直线方程），即：

$$ T(n)=T(\frac nb)+(kn+p)\tag{$b>1,k>0,p$为某个常数} $$

则：

$$ T(n)=Θ(n) $$

证明 应用分治法中式$(2.2.8)$：

$$ \begin{align} T(n)&=n^{log_ba}[T(1)+\sum_{j=1}^{log_bn}{\frac {f(b^j)}{a^j}}]\tag{3.2.1}\\ &=\sum_{j=1}^{log_bn}{(kb^j+p)}\tag{3.2.2}\\ &=plog_bn+\frac {kb}{b-1}(n-1)\tag{$k>0,p>0,b>1$}\\ &<pn+\frac {kb}{b-1}(n-1)\tag{3.2.4}\\ &=cn-\frac {kb}{b-1}\tag{$c>0$且为某个常数}\\ &=Θ(n)\tag{3.2.5} \end{align} $$

证明成立。

四：总结

第一部分辨析了$O,Ω,Θ$三种符号的区别以及它们的性质。

第二部分介绍了两种常用的计算时间复杂度方法，即主定理和分治法。

第三部分给出了个人在演算时发现的两个定理，并给出了证明，题外话，这两条定理比较实用，希望读者能够熟记。另外如果您在其它网站看到类似原创定理，纯属巧合。

五：参考文献

• 算法设计与分析基础（第3版）. Page 40-45，Page 376.
• 维基百科. 主定理.