渐近符号

算法复杂度的表示通常用三种渐进符号:$O, Ω, Θ$。我们平时常见的都是第一个,后面两个多见于教科书。下面先介绍下这三种符号的含义和性质。

符号 $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)\\ 100n+5&=O(n^2)\\ \frac 12n(n-1)&=O(n^2)\\ n^3&≠O(n^2)\\ 0.00001n^3&≠O(n^2) \end{align} $$

符号 $Ω$

$Ω$,读作 "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)\\ \frac 12n(n-1)&=Ω(n^2)\\ 100n+5&≠Ω(n^2) \end{align} $$

符号 $Θ$

读作 "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) \end{align} $$

三种符号的性质

性质 如果 $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)\\ &≤c_3g_1(n)+c_3g_2(n)=c_3[g_1(n)+g_2(n)]\\ &≤c_3⋅2\max\{g_1(n),g_2(n)\} \end{align} $$

也就是说,对于两个连续执行部分组成的算法,它的整体效率是由具有较大增长次数的部分所决定的,即效率较差的部分决定

举个例子,如下代码的复杂度可以直接表示为 $O(n^2)$,

void func(int n)
{
    for (int i = 0; i < n; ++i) // O(n)
        ;
    
    for (int i = 0; i < n; ++i) // O(n*n)
        for (int i = 0; i < n; ++i)
            ;
}

计算复杂度

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

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

$$ 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)$ 包含了问题分解和子问题解合并的代价。

举个例子,以下的递归求和函数的方程式为 $T(n) = T(n-1) + O(1)$,

int GetSum(int n)
{
    if (n == 1)
        return 1;
    
    return n + GetSum(n - 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)) $$

算法导论已有关于这个定理的证明,篇幅较长,故此处省略,有兴趣的读者可以自己去翻阅下。

分治法

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

$$ \begin{align} T(n)&=aT(\frac nb)+f(n)\tag{($2.1$) 递归方程式}\\ T(b^k)&=aT(b^{k-1})+f(b^k)\\\ &=a[aT(b^{k-2})+f(b^{k-1})]+f(b^k)=a^2T(b^{k-2})+af(b^{k-1})+f(b^k)\\ &=a^3T(b^{k-3})+a^2f(b^{k-2})+af(b^{k-1})+f(b^k)\\ &=...\\ &=a^kT(1)+a^{k-1}f(b^1)+a^{k-2}f(b^2)+...+a^0f(b^k)\\ &=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$} $$

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

定理 1

定理 1 对于 $(2.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$,证明成立。

定理 2

定理 2 对于 $(2.1)$ 递归方程式,若 $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}}]\\ &=\sum_{j=1}^{log_bn}{(kb^j+p)}\\ &=plog_bn+\frac {kb}{b-1}(n-1)\tag{$k>0,p>0,b>1$}\\ &<pn+\frac {kb}{b-1}(n-1)\\ &=cn-\frac {kb}{b-1}\tag{$c>0$ 且为某个常数}\\ &=Θ(n) \end{align} $$

证明成立。

参考

  • 《算法设计与分析基础》
  • 维基百科. 主定理

其它

文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。

如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨给个 Star,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2018-04-05
原文链接:https://ethsonliu.com/2018/04/algorithm-complexity.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。