算法的原理和核心思想

内容摘要

这篇博文主要讲述了算法的定义、核心思想和使用范围，介绍了渐进分析法用以分析算法的时间复杂度。同时举例说明了三种常用计算时间复杂度的方法。¹ ² ³

算法前言

算法的定义

算法是任何能把一系列输入变成一系列输出的良定义（well-defined）计算程序。

所以算法是能把输入转换成输出的一系列有序步骤。

学习算法的意义

算法和计算机硬件一样是一门技术。
学习一些算法设计与分析的技术，以便我们自己能够看懂算法，分析算法，理解其效率。甚至自行设计算法和证明其正确性。

循环不变式

我的理解：某个序列在循环前中性质不变，循环终止后，通过每一次的迭代，得到我们想要的结果。

充要条件：

初始化：循环的第一次之前，它为真。

保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。

终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

可以把循环不变式看成算法分析设计的启发式思想。

评判算法的标准

正确性
简易性
最优性
完成的工作量
使用的空间

伪代码的阅读规则小结

~~为什么伪代码还有阅读规则呀，按理来说伪代码不是想怎么写就怎么写吗？~~

开头描述输入输出。
伪代码的语法关键字全部大写。
只有局部变量，没有全局变量。
每一行伪代码前必须要有序号。
while后面直接跟条件。后面的语块中跟缩进的do。
1
2
WHILE i>0 AND A[i]>key
DO key <- val
for：直接跟循环值，且to代表从前到后，downto代表从后到前。
1
2
FOR j <- 2 TO A.length
FOR i <- A.length DOWNTO 2
多重赋值：i=j=val。
if后面要跟then语句块。elseif要写在一起。else后面可以不跟then。

规则

算法时间复杂度分析——渐进分析

基本概念

引入时间复杂度，与软件、硬件、接口等通通无关，只与规模有关。并且通过图形验证（课上的证明只有一元变量），当$n$->$\infty$时，最高次一样的图形通通重合。

特点：

基于基本操作数和输入数。因为一个机器的基本操作所花的时间是常数$c$.

优点：

可以规避除算法之外的其他因素干扰（软件、硬件、接口）
将运行时间和输入量联系起来
忽略常数时间
可以简化描述

渐进函数记号

渐进紧确界$\Theta$

英文名asymptotically tight bound

对给定的一个函数$g(n)$，用$\Theta(g(n))$来表示以下函数的集合： \[ \Theta(g(n))= \{ f(n)| \ \exists正常量c_{1}、c_{2}和n_{0},使得对所有n\geq n_{0},有0\leq c_{1}g(n)\leq f(n)\leq c_{2}g(n) \} \] $g(n)$就被称为$f(n)$的一个渐进紧确界。

用极限的写法：

因为$g(n)$是正函数，所以$\exists\ \varepsilon > 0$，得： \[ \begin{aligned} 0\leq c_{1}g(n)\leq f(n)\leq c_{2}g(n) &=>c_{1}\leq\frac{f(n)}{g(n)}\leq c_{2}\\ &=>c-\varepsilon \leq \frac{f(n)}{g(n)} \leq c+\varepsilon \\ &=>|\frac{f(n)}{g(n)}-c|_{(n->\infty)}\leq\varepsilon \end{aligned} \]

即$\lim_{n->\infty}\frac{f(n)}{g(n)}=c$.

渐进上界$

英文名upper bounds

对给定的一个函数$g(n)$，用$\Theta(g(n))$来表示以下函数的集合：

\[ \Theta(g(n))= \{ f(n)| \ \exists正常量c和n_{0},使得对所有n\geq n_{0},有0\leq f(n)\leq cg(n) \} \] $g(n)$就被称为$f(n)$的一个渐进上界，一般我们找的是最紧上界。

用极限的写法为：$\lim_{n->\infty}\frac{f(n)}{g(n)}\le c$.

上界平时使用的更多

因为在生产中，我们对最差情况更感兴趣，并且上界比紧确界更好找。

渐进下界 $\Omega$

英文名lower bounds

对给定的一个函数$g(n)$，用$\Theta(g(n))$来表示以下函数的集合：

\[ \Theta(g(n))= \{ f(n)| \ \exists正常量c和n_{0},使得对所有n\geq n_{0},有0\leq cg(n)\leq f(n) \} \] $g(n)$就被称为$f(n)$的一个渐进下界，一般我们找的是最紧下界。

用极限的写法为：$\lim_{n->\infty}\frac{f(n)}{g(n)}\geq c$.

其他记号

$o$记号和$\omega$记号，只是因为数学的完整性才保留它的，实际生产中并没有什么用。

定理（部分）

任意$f(n)$和$g(n)$，有$f(n)=\Theta(g(n))$，当且仅当$f(n)=O(g(n))$且$f(n)=\Omega(g(n))$.
传递性：上界的上界仍是上界，下界的下界仍是下界，紧确的紧确仍是紧确。
自反性：自己是自己的上界，自己是自己的下界，自己是自己的紧确。
对称性&转置对称性：

$f(n)=\Theta(g(n))当且仅当g(n)=\Theta(f(n))$

$f(n)=O(g(n))当且仅当g(n)=\Omega(fn)$
三分性：即$\Theta,O,\Omega$至少占一种，但是不是所有的函数都是可渐进比较的。

渐进关系中的一些等式

$O(f(n)+g(n))=O(max{f(n),g(n)})$
$\mathrm{O}(f(n))+\mathrm{O}(g(n))=\mathrm{O}(f(n)+g(n))$
$O(f(n)) \cdot O(g(n))=O(f(n) \cdot g(n))$
$O(c \cdot f(n))=O(f(n))$

常见渐进函数

从小下大： \[ \begin{array}{l} O(1) \\ O(\log (n)) \\ O(n) \\ O(n \log (n)) \\ O\left(n^{2}\right) \\ O\left(n^{3}\right) \\ O(n !) \end{array} \]

求渐进函数的经验方法

在工程上

只保留最高级别的项，去掉其他项。去掉最高级别的常数。注意，所以的记号都是，包括$\Omega$，所以求下界时也会出现只剩较大函数的情况，eg：$\Theta\left(n^{1.2}\right)+O\left(n^{3} \log \log (n)\right)+\Omega(\sqrt{n})=\Omega(n^{1.2})$
所有基数为$b$的对数函数都是$log_{b}n= \Theta(ln(n))$. 但是指数函数确没有相应规则（但实际我们一般也不会将指数函数当成我们的结果）
一般都是用极限定义的方法，寻找$n_{0}$和$c$.
相同渐进方式下的关系(以$O$为例) \[ \begin{aligned} & O(f(n))+O(g(n)) = O(max{f(n), g(n)}) \\ & O(f(n))+O(g(n)) = O(f(n)+g(n)) \\ & O(f(n)) ·O(g(n)) = O(f(n) ·g(n)) \\ & O(c·f(n)) = O(f(n))\\ \end{aligned} \]
不同渐进方式下的关系 \[ O(f(n))+\Theta(g(n)) = \Theta(max\{ f(n), g(n) \}))\\ or\\ O(f(n))+\Theta(g(n)) = O(max\{ f(n), g(n) \})) \] 原因：由_定理1_可知，$\Theta(n)$已经蕴含$O(n)$了。注意：第一个式子中$\Omega$也只保留去掉系数的最高项。
对于多元变量的渐进分析：因为我们不知道两个变量之间的关系，所以在这个条件下我们不可以和一元变量进行比较。

以上都是工程上的方法，如果要证明$\Theta(f(n))+\Theta(g(n))=\Theta(f(\mathrm{n})+g(n))$得用数学方法

简单代码中的渐进分析

几条简单的原则：

代码中的每次一操作都是常数级别的操作，包括开内存和储存（虽然实际情况中可能不是这样）
非嵌入的代码块之间的渐进函数应该是相加

注意：switch和if-else在渐进计算中是一样的，所以switch的渐进函数的计算要看case的个数以及case内部的复杂度（所以基本上也是n）。本质上是+
嵌入代码块中的代码应该_从内到外_进行展开计算（像for、while之类的）

实例：对于代码
1
2
3
4
5
6
7
int sum = 0;
int n;
for (int i=0;i<n;i++){
for (int j=0;j<i;j++){
sum += (i+j);
}
}
它的内层循环为：$\Theta(1+i(1+1))$：第一个$1$，初始化j；$i$，循环$i$次；$(1+1)$，加一次，赋值一次

外层循环为：$\Theta(1+(\sum^{n}_{i=0}1+i))$：第一个$1$，初始化i；中间比较操作，循环$n$次；最后一个$i$，因为内层for已经被我们算出来为$\Theta(i)$了，所以直接加

最后算出来是：$\Theta(1+(\sum^{n}_{i=0}1+i))=\Theta(1+n+\sum^{n}_{i=0}i)=\Theta(n^{2})$
在代码块中有函数，应该是块中其他内容的渐进函数+被调函数的渐进函数。其中return操作是常数

算法的核心思想——分治策略

概述

分治的一般步骤：

分解（Divide）：按步骤将复杂问题分解成小问题，直到问题可以直接求解。
解决（Conquer）：求解规模足够小的问题，比如当递归排序减小到只有八个数的时候就可以用插入排序来解决了。
合并（Combine）：逐步将小问题的解合并成原问题的解。

分治中的渐进分析

在递归中，我们通常可以得到一个关于最小问题的渐进函数和原问题的递推公式（recurrence）。我们可以用以下方法找出渐进函数：

1.递归树法（Recursion-tree）

说明：将递归过程拆分成一个计算式，然后每一个节点表示解决这个层次问题的代价，然后从叶子节点开始一个一个地向上求解。原问题的复杂度可以近似为整个数之和。有些递归式形式较为特殊，最终可以构造成总代价=每层代价*层数

优点：便于理解；便于计算。
缺点：它并不是一个严格的数学方式，只能是一个具体问题的具体分析。因为它并不是一个完全的展开。所以在正式场合不单独使用，而是作为猜测方法配合代入法来使用。

过程：我们将某个递归式按照树形结构进行展开，然后将每一层加起来。对于递推式无法合并且含有表达式或可以转换成表达式的部分，我们需要将表达式部分拉出来作为该节点的代价，然后将递推部当做下一个深度的节点，以此类推。可以用缩放的方法来考虑上下限。如：

说明一共有多少层，每层代价是多少，则总的时间复杂度为层数 * 每层代价

2.主方法（也叫展开法）

说明：将递推公式（也叫递归式），按照递推内容展开，通过这个过程，我们找到关于该递归式的一定规律(这个也是必要条件)。主方法可以求解形如此的公式 \[ T(n)=aT(n/b)+f(n) \] 其中$a\ge 1,b>1,f(n)$是一个给定的函数。我们的方法就是将其展开后，算一个数列求和。

一些示例：

$T(n)=aT(n/b)+\Theta(g(n))$:

主要是后面的$\Theta(g(n))$的处理。因为$\Theta$是紧确界，所以我们可以找一个大于0的常数$c_{1}$来表示成： \[ T(n)=aT(n/b)+c_{1}g(n) \] 这样到最后依然是一个紧确界。
$T(n)=aT(n/b)+O(g(n))$:

这次的区别为后面是上界。那同理，我们可以得到这个式子： \[ T(n)\le aT(n/b)+c_{1}g(n) \] 这样处理到后面依然是上确界。
$T(n)= \begin{Bmatrix} &\Theta(1),n=1\\ &2T(n/2)+\Theta(n),n>1 \end{Bmatrix}$

我们考虑如下过程： \[ \begin{aligned} T(n)&=2T(\frac{n}{2})+cn\\ &=4T(\frac{n}{4})+2c\frac{n}{2} +cn\\ &=8T(\frac{n}{8})+4c\frac{n}{4}+2c\frac{n}{2}+cn\\ &=\ ...\\ &=2^{k}T(\frac{n}{2^{k}})+c(2^{k-1}\frac{n}{2^{k-1}}+...+2\frac{n}{2}+n)\\ &直到\frac{n}{2^{k}}=1时，k=log(n)\\ 则原式&=2^{log(n)}T(1)+ckn\\ &=n\Theta(1)+cnlogn\\ &=c_{2}n+cnlogn\\ &=\Theta(c_{1}+cnlogn)\\ &=\Theta(nlogn) \end{aligned} \]
解释一下是怎么从$2^{log(n)}T(1)+ckn$变成$n\Theta(1)+cnlogn$的：
- 条件中就给出$T(1)=\Theta(1)$了
- 当$k=log(n)$时，$2^k=2^{log(n)}=n$，下面的式子正式建立在$k=log(n)$的基础上的。
$\mathrm{T}(n)=\left\{\begin{array}{cc}1 & n=1 \\ \mathrm{~T}\left(\frac{n-1}{2}\right)+1 & n>1\end{array}\right.$ 这样直接展开或许有点困难，我们将$n$赋予特殊的值，令$n=2^{k}-1$，这样就可以解下去了，最后算出结果是$\mathrm{T}(n)=\Theta(\log (n))$

3.代入法（substitution）

是一种数学归纳法：

猜测解的形式（可用递归树法和展开法辅助猜测）
用数学归纳法求解出解中的常数，并且证明解是可行的。

首先根据$O,\Omega,\Theta$来猜测$T(n)\le f(n)$，然后将$f(n/b)$带入递推式$T(n)=aT(n/b)+h(n)$，通过一系列变换推出$T(n)\le f(n)$这一式子，该式子形式上必须严格与猜测的式子相同。如果要证明$\Theta$的话，那$O,\Omega$都需要证明。