本站经典算法总结

分治策略与求解Divide & Conquer
贪心算法问题与证明Greedy Algorithm
谈谈，动态规划Dynamic Programming
排序算法全TIPS收集企划Sort Algorithm
选择算法全收录Select Algorithm
斐波那契与快速幂Wonderful Fibonacci

什么是算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中，以及在此基础上为实现某个功能(比如查找某个元素，删除某个元素，对所有元素进行排序)而执行的相应操作， 这个相应的操作也叫算法

算法的特征

算法具备下列 5 种 特征：

  1. 输入| Input：一个算法需要零个或多个输入
  2. 输出| Output：一个算法至少给出一个输出
  3. 确定性| definiteness：算法的每一条指令应有明确的定义，无二义性
  4. 可行性| effectiveness：算法的每一条指令必须足够基础，可通过已实现的基本运算执行有限次实现
  5. 有限性| finiteness：算法必须始终在执行有限步之后有效停止

而一个 好的算法 应具有下列 4 种特征：

  1. 正确性| correctness：算法的执行结果应满足预先设定的功能或要求
  2. 简明性| simplicity：算法应思路清晰，层次分明，容易理解，利于编码，便于调试
  3. 效率性| efficiency：算法应有效使用存储空间，并具有高的时间效率
  4. 最优性| optimality：算法的执行时间应达到求解该类问题所需时间的下界

此外，人们往往需要算法能够对一些非法输入或者异常情况进行适应和处理而非直接导致程序错误，由此引入了 健壮性|robustness（也译作 鲁棒性）和 可靠性| reliability。

算法分析基础

时空复杂度

待更

函数的渐近界

渐近情况示意图

渐近上界|大 O 记号

定义 设ff和gg是定义域为自然数集NN上的函数，若∃c,n0>0\exists c,n_0>0使得，∀n≥n0\forall n\geq n_0:

0≤f(n)≤cg(n)0\leq f(n)\leq cg(n)

则称：f(n)f(n) 的渐近的上界是g(n)g(n)， 记作：

f(n)=O(g(n))f (n) = O\left(g(n)\right)

非渐近紧确上界|小 o 记号

定义 设ff和gg是定义域为自然数集NN上的函数，若∀c>0,∃n0>0\forall c>0,\exists n_0>0使得，∀n≥n0\forall n\geq n_0:

0≤f(n)≤cg(n)0\leq f(n)\leq cg(n)

则记作：

f(n)=o(g(n))f (n) = o\left(g(n)\right)

定理 如果lim⁡n→∞f(n)g(n)=0\lim_{n\to\infty}\frac{f(n)}{g(n)}=0，那么f(n)=o(g(n))f (n) = o\left(g(n)\right).

*回忆 高等数学 中，对 高阶无穷小 的记号

渐近下界|大 Ω 记号

定义 设ff和gg是定义域为自然数集NN上的函数，若∃c,n0>0\exists c,n_0>0使得，∀n≥n0\forall n\geq n_0:

0≤cg(n)≤f(n)0\leq cg(n)\leq f(n)

则称：f(n)f(n) 的渐近的下界是g(n)g(n)， 记作：

f(n)=Ω(g(n))f (n) = \Omega\left(g(n)\right)

非渐近紧确下界|小 ω 记号

定义 设ff和gg是定义域为自然数集NN上的函数，若∀c>0,∃n0>0\forall c>0,\exists n_0>0使得，∀n≥n0\forall n\geq n_0:

0≤cg(n)≤f(n)0\leq cg(n)\leq f(n)

则记作：

f(n)=ω(g(n))f (n) = \omega \left(g(n)\right)

定理 如果lim⁡n→∞f(n)g(n)=∞\lim_{n\to\infty}\frac{f(n)}{g(n)}=\infty，那么f(n)=ω(g(n))f (n) = \omega\left(g(n)\right).

渐近紧确界| Θ 记号

定义 若f(n)=O(g(n))f(n)=O(g(n))且f(n)=Ω(g(n))f(n)=\Omega (g(n))，则记作：

f(n)=Θ(g(n))f(n)=\Theta(g(n))

表明：f(n)f(n)与g(n)g(n) 同阶

定理 如果lim⁡n→∞f(n)g(n)=c>0\lim\limits_{n\to\infty}\frac{f(n)}{g(n)}=c>0，那么f(n)=Θ(g(n))f (n) = \Theta\left(g(n)\right).

证明

根据极限定义，对于给定正数ε\varepsilon，∃n0\exists n_0 使得当n≥n0n\geq n_0时：

∣f(n)g(n)−c∣<εc−ε<f(n)g(n)<c+ε\begin{aligned}\left|\frac{f(n)}{g(n)}-c\right|&\lt\varepsilon\\c-\varepsilon\lt\frac{f(n)}{g(n)}&\lt c+\varepsilon\end{aligned}

取ε=c/2\varepsilon=c/2 于是，有：

c/2<f(n)g(n)<3c/2<2cc/2\lt \frac{f(n)}{g(n)}\lt 3c/2 \lt 2c

因此，∀n≥n0\forall n \geq n_0，有f(n)≤2cg(n)f(n)\leq 2cg(n)，即f(n)=O(g(n))f(n)=O(g(n))

∀n≥n0\forall n \geq n_0，有f(n)≥c2g(n)f(n)\geq \frac c 2 g(n)，即f(n)=Ω(g(n))f(n)=\Omega(g(n))

所以：f(n)=Θ(g(n))f (n) = \Theta\left(g(n)\right)

证毕.

传递性

设函数f,g,hf,g,h的定义域为自然数集合，有：

  1. 如果f=O(g)f=O(g)，且g=O(h)g=O(h)，则f=O(h)f=O(h).
  2. 如果f=Ω(g)f=\Omega(g)，且g=Ω(h)g=\Omega(h)，则f=Ω(h)f=\Omega(h).
  3. 如果f=Θ(g)f=\Theta(g)，且g=Θ(h)g=\Theta(h)，则f=Θ(h)f=\Theta(h).

叠加性

设函数f,g,hf,g,h的定义域为自然数集合，有：

如果f=O(h),g=O(h)f=O(h),g=O(h)，则f+g=O(h)f+g=O(h).

该性质可以扩展到有限个函数

其他性质

若f1(n)=O(g1(n)),f2(n)=O(g2(n))f_1(n)=O(g_1(n)),f_2(n)=O(g_2(n))，有：

f1(n)+f2(n)=O(max⁡{g1(n),g2(n)})f1(n)+f2(n)=O(g1(n)−g2(n))\begin{aligned} f_1(n)+f_2(n)&=O(\max\{g_1(n),g_2(n)\})\\ f_1(n)+f_2(n)&=O(g_1(n)-g_2(n)) \end{aligned}

本题摘自《算法设计与分析》陈慧南第三版第2章课后习题

常见函数的阶数比较

Tips: 在算法分析中，一般默认log⁡()\log()是以2为底的对数函数，即log⁡2()\log_2().

事实上在函数渐近界领域对于对数的底数因为只差一个常数系数，即有：log⁡2n=Θ(log⁡ln)\log_2 n = \Theta(\log_l n)

因此，底数对分析算法复杂度上并没有影响。

阶排序

常见的函数的速度

  1. 多项式函数的阶低于指数函数：nα=o(rn),r>1,α>0n^\alpha=o(r^n),r\gt 1,\alpha\gt 0
  2. 对数函数的阶低于幂函数：log⁡n=o(nα),α>0\log n=o(n^\alpha),\alpha\gt 0
  3. 阶乘：n!=o(nn);  n!=ω(2n);  log⁡(n!)=Θ(nlog⁡n)n!=o(n^n);\;n!=\omega(2^n);\;\log (n!)=\Theta(n\log n)

22n>n!>n2n>2n>(32)n>nlog⁡log⁡n=(log⁡n)log⁡n>n3>n2>log⁡(n!)=Θ(nlog⁡n)>2log⁡n=n>log⁡2n>log⁡n>log⁡n>log⁡log⁡n>n1/log⁡n=1\begin{aligned} 2^{2^n}\gt n!\gt n2^n\gt 2^n\gt(\frac 3 2)^n\gt n^{\log\log n}=(\log n)^{\log n}\gt\\ n^3\gt n^2\gt \log(n!)=\Theta(n\log n)\gt2^{\log n}=n\gt\log^2n\gt\\ \log n\gt\sqrt{\log n}\gt\log\log n\gt n^{1/\log n}=1 \end{aligned}

取整函数的性质

  1. x−1<n=⌊x⌋<x<⌈x⌉=n<x+1x-1\lt n=\lfloor x\rfloor \lt x\lt \lceil x\rceil =n\lt x+1
  2. ⌈x/k⌉=⌊(x+k−1)/k⌋\lceil x/k\rceil=\lfloor(x+k-1)/k\rfloor
  3. ⌊x+n⌋=⌊x⌋+n,  ⌈x+n⌉=⌈x⌉+n\lfloor x+n\rfloor = \lfloor x\rfloor +n,\;\lceil x+n\rceil = \lceil x\rceil +n
  4. ⌊n2⌋+⌈n2⌉=n\begin{aligned}\left\lfloor\frac{n}{2}\right\rfloor+\left\lceil\frac{n}{2}\right\rceil=n\end{aligned}
  5. ⌊⌊na⌋b⌋=⌊nab⌋,  ⌈⌈na⌉b⌉=⌈nab⌉\begin{aligned}\left\lfloor\frac{\left\lfloor\frac{n}{a}\right\rfloor}{b}\right\rfloor=\left\lfloor\frac{n}{ab}\right\rfloor,\;\left\lceil\frac{\left\lceil\frac{n}{a}\right\rceil}{b}\right\rceil=\left\lceil\frac{n}{ab}\right\rceil\end{aligned}

递推关系分析

设序列a0,a1,…,an,…a_0 , a_1 , …, a_n , … 简记为{an}\{a_n\}, 一个把ana_n与某些个ai(i<n)a_i\quad (i\lt n) 联系起来的等式称为关于序列{an}\{a_n\}的递推方程，也叫递推式、递归式等。

而给定递推方程和若干个初值，计算ana_n的通式就称为递推方程的求解。

在算法分析中，我们着重关心一个算法的时间复杂度，而时间复杂情况往往与输入数据的规模有关，我们记为T(n)T(n).
那么，如果我们能够将算法时间的递推方程描述出来，就能够用求解递推方程的相关数学方法对其进行求解了。

一般情况下，算法的时间可以用形如：

T(n)=∑ibiT(li(n))+f(n)T(n)=\sum_ib_iT(l_i(n))+f(n)

的递推式进行刻画。
即 规模为nn的问题，其时间可以用若干个规模为li(n)<nl_i(n)\lt n的子问题时间的线性组合，再加上非递归代价f(n)f(n)组成。

偶尔我们也会遇见非递归方程，而是不等式的形式出现的递归式，如T(n)≤T(n/2)+Θ(n)T(n)\leq T(n/2)+\Theta(n)。
此时我们可以借助不等式一侧的递推关系来确定上界或下界。

下面我们将介绍求解递归式的几种常用方法，进而得到算法的Θ\Theta或OO渐近界。

代入法

代入法 也叫 替代法，主要思想是通过列写几个确定 n 并且通过递推式得出的结果进行分析，猜测出对应的通式或界，最后利用数学归纳法进行证明。
该方法比较考验数学归纳的能力，但是一旦总结出来后就很容易证明。

例如：T(n)=T(n−1)+1,T(1)=1T(n)=T(n-1)+1,T(1)=1

迭代法

待更

差消法

以快速排序计算 平均时间复杂度 为例对差消法进行阐述。

假设 枢轴/基准/首元素 在一趟排序后的位置服从于均匀分布U(p,r)U(p,r). 即其在每一个位置的概率相等且为1/n1/n. 那么：

情况子数组的求解时间子数组的求解时间
A[1]=xA[1]=xT(0)T(0)T(n−1)T(n-1)
A[2]=xA[2]=xT(1)T(1)T(n−2)T(n-2)
A[3]=xA[3]=xT(2)T(2)T(n−3)T(n-3)
………
A[n]=xA[n]=xT(n−1)T(n-1)T(0)T(0)

每个情况下划分时间代价的总和为n−1n-1

于是得到平均时间代价：

T(n)=1n∑k=0n−1[T(k)+T(n−k)]+(n−1)=2n∑k=0n−1T(k)+(n−1)⇒{nT(n)=2∑k=0n−1T(k)+n2(n−1)T(n−1)=2∑k=1n−2T(k)+(n−1)2nT(n)−(n−1)T(n−1)=2T(n−1)+2n−1⇒T(n)=Θ(nlog⁡n)\begin{aligned} T(n)&=\frac{1}{n}\sum_{k=0}^{n-1}[T(k)+T(n-k)]+(n-1)\\ &=\frac{2}{n}\sum_{k=0}^{n-1}T(k)+(n-1)\\\\ \Rightarrow&\begin{cases}nT(n)&=2\sum\limits_{k=0}^{n-1}T(k)+n^2\\ (n-1)T(n-1)&=2\sum\limits_{k=1}^{n-2}T(k)+(n-1)^2\end{cases}\\\\ &nT(n)-(n-1)T(n-1)=2T(n-1)+2n-1\\\\ \Rightarrow& T(n)=\Theta(n\log n) \end{aligned}

递归树|Recursion tree

Recursion Tree 将递归式转换为一棵树，树的结点表示不同层次的递归调用产生的代价，然后利用边界进行求解。

当T(n)T(n) 依赖于几个不连续的前项时，使⽤递归树解递推⽅程通常更有效。

  • 递归树是迭代计算/迭代过程的模型；
  • 递归树的生成过程与迭代过程⼀致；
  • 递归树上所有结点恰好是迭代之后产生和式中的项；
  • 对递归树上的所有结点（中间结点、叶⼦、根）求和就是迭代后方程的解。

递归树的生成

递归树的生成过程如下：

  1. 初始只有根节点T(n)T(n)；
  2. 不断地将函数项结点⽤二层子树结构替换：该子树根为T(ni)T(n_i)，叶⼦为更小的函数项；
  3. 当函数项已缩小至初始值，递归树生长完成。

以二分归并排序算法为例，生成完整的递归树之后，计算每一层的代价（右边红框处），然后将它们累加起来就能得到该算法总体的时间代价了。
二分归并排序的递归树

主定理|Master Theorem

对于递归算法，常常可以将算法规模总结为如下递归式：

T(n)=aT(n/b)+f(n)T(n)=aT(n/b)+f(n)

式中，a≥1,b>1a\geq1,b\gt1为常数，f(n)f(n)为渐近正函数，n/bn/b可以指⌊n/b⌋\left \lfloor n/b \right \rfloor 或⌈n/b⌉\left\lceil n/b\right\rceil

对于这类递推式的求解，可以直接利用主定理：

  1. 若∃ε>0\exists\varepsilon\gt0，有f(n)=O(nlog⁡ba−ε)f(n)=O(n^{\log_ba-\varepsilon})，则T(n)=Θ(nlog⁡ba)T(n)=\Theta(n^{\log_ba})；
  2. 若f(n)=Θ(nlog⁡ba)f(n)=\Theta(n^{\log_ba})，则T(n)=Θ(nlog⁡balog⁡n)T(n)=\Theta(n^{\log_ba}\log n)；
  3. 若∃ε>0\exists\varepsilon\gt0，有f(n)=Ω(nlog⁡ba+ε)f(n)=\Omega(n^{\log_ba+\varepsilon})，且∃c<1\exists c\lt1与所有足够大的nn，有af(n/b)≤cf(n)af(n/b)\le cf(n)，则T(n)=Θ(f(n))T(n)=\Theta(f(n)).
主定理的证明

主定理的简化版本

定义h(n)=nlog⁡bah(n)=n^{\log_ba} ，则主定理可以表示为：

T(n)={Θ(h(n)),f(n)=o(h(n))Θ(h(n)log⁡n),f(n)=Θ(h(n))Θ(f(n)),f(n)=ω(h(n))∧∃c<1  s. t. af(nb)≤cf(n)T(n)=\begin{cases} \Theta(h(n)),&f(n)=o(h(n))\\ \Theta(h(n)\log n),&f(n)=\Theta(h(n))\\ \Theta(f(n)),&f(n)=\omega(h(n))\land\exists c\lt1\;\text{s. t. }af(\frac nb)\leq cf(n) \end{cases}

注意此处的是小oo 和小ω\omega.

参考

  1. 《算法导论(原书第三版)》
  2. 《算法设计与分析(第3版)》，陈慧南著
  3. 算法设计与分析|中国大学MOOC