算法分析

什么是算法

算法是对特定问题求解步骤的一种描述，是指令的有限序列

从上面的描述中我们可以看出算法强调的是解题步骤，而不是具体求解问题的具体代码指令。

思考：程序==算法？

程序不等于算法，程序是算法用某种程序设计语言的具体实现，所以可以看出算法一种脱离于编程语言限制的抽象化得解题思路，所以算法可以说永远不会过时，而程序则可能会一直变化使用更优秀的编程语言来编写。

算法的特点

• 输入：算法有零个或多个输入量（一定要注意是可以没有输入的）
• 输出：算法至少要产生一个输出量
• 确定性：算法的每一条指令都有确切的定义，没有二义性
• 能行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现
• 有穷性：算法必须总能在执行有限步之后终止

思考：OS是程序还是算法？

我们学习了OS后知道OS实质上也是一个运行于硬件层上的软件程序，只不过他比较特殊是一个在无限循环中执行的程序，因而不是一个算法。但是操作系统的各种任务可以看成是单独的问题，每一个问题由操作系统中的一个子任务通过特定的算法来实现，该子程序得到输出结果后就终止。

算法应用的问题

1. 搜索问题（在给定的数据集合中寻找满足条件的数据对象）
2. 排序问题（把无需的数据按照一定的规则排列）
3. 图论问题（一般数据结构是图形结构或者树形结构，常用于解决交通，通讯，工程项目时间表和各种流量问题）
4. 组合数学问题（例如图着色或者TSP旅行商等）
5. 几何问题（凸包等）
6. 数值计算（估算最大或最小值，常常不能给出精确值）

十大经典算法实例

1. 蒙特卡罗算法（随机性模拟算法，通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，是比赛时必用的方法）
2. 数据拟合，参数故居，插值等数据处理算法（大数据处理，常常需要借用matlab作为工具）
3. 线性规划，整数规划，多元规划，二次规划等规划类问题（建模竞赛大多数属于最优化问题，很多时候这些问题可以用数学规划类算法描述，常借用Lindo,Lingo等软件实现）
4. 图论算法（最短路，网络流，二分图等算法）
5. 动态规划(dp)，回溯搜索（tranceback),分枝限界等计算算法。
6. 最优化理论的三大非经典算法：模拟退火法，神经网络，遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，但是实现困难）
7. 网络算法和穷举法（暴力搜索最优点的算法，模拟常用）
8. 连续离散化方法（以离散极限模拟连续）
9. 数值分析法（方程组求解，矩阵运算，函数积分等算法）
10. 图像处理算法

算法的复杂性

空间复杂度

空间复杂度是指程序运行时所需的内存空间大小和实例特征的函数关系，一般所需空间包括：

1. 指令空间（常数，与实例无关的有限整数）
2. 数据空间：常量和简单变量与实例无关，但是复合变量（如数组，链表，树和图等）以及环境栈空间（函数调用需要）大小与实例和是否递归有关。

对于非递归的算法，一般分析实例有关的数据结构大小即可分析出空间复杂度，而对于递归算法还要讨论递归调用的深度和实例的关系。

时间复杂度

指程序执行时所用的时间，一般与循环层次，递归调用深度，算法性能有关。除了优先指令所运行的基本操作固定步数时间以及输入输出的有限时间，时间复杂度主要是与运行的深度呈正相关。一般对于不同的实例特征，同一个算法对应的时间复杂度也不一定相同，一般可分为最好，最坏和平均时间复杂度。一般算法的整体性能好坏由最坏时间复杂度和平均时间复杂度决定。

算法渐进符号分析

对于算法的性能我们通常会用到渐进分析符号来表示算法的上界或者下界。这里一般会用到三种符号

O–渐进上界

$$\lim_{n\rightarrow+\infty}{|fn/gn|}=c,c>1\\ 则fn=O(gn)$$

f(n)=O(g(n)) 当且仅当存在常数c和n0使得对所有n>n0 有f(n)<cg(n) 成立。即O表示一个算法的上界，例如：O(n)表示这个算法最大的复杂度f(n)一定存在一个常数c使得c*n>f(n)。例如f(n)=n^3+20n^2+6n-10000=O(n^3)

Ω–渐进下界

$$\lim_{n\rightarrow+\infty}{|fn/gn|}=c,0<c<1\\ 则fn=Ω(gn)$$

f(n)=Ω(g(n)) 当且仅当 存在常数c和n0使得对所有n>n0,有f(n)>cg(n*)成立。即Ω表示一个算法的下界，例如：Ω（n)表示这个算法小的复杂度f(n)一定存在一个常数c使得c(n)<f(n)。例如fn=(0.001)n^2-10n-1000=Ω（n^2)

Θ–同阶

$$\lim_{n\rightarrow+\infty}{|fn/gn|}=c,c=1\\ 则fn=Θ(gn)$$

如果f(n)=O(g(n))同时 f(n)=Ω(g(n))则f(n)=Θ(g(n)),并称f(n)与g(n)同阶。即渐进上界和渐进下界都逼近于一个量级，则就说这个算法的复杂度f(n)=Θ(g(n))，例如fn=(n^2.8)+10000=Θ(n^2.8)

特殊地，我们约定O(1)代表常数，因为对于任意一个复杂度为k的复杂度，我们都存在一个常数c=k+1使得c*O(1)>k。对于g(n)函数我们一般尝试取n^k,log2n,n^klog2n等进行估计。

几种g(n)的增长率

一般算法时间复杂度为nlogn,n或者logn为较为优秀的算法，2^n就非常糟糕，n^2还可以接受但是也不是特别好，一般能避免尽量避免。

伪代码

一般算法可以在任何一种语言下都可以具体实现，但是为了具体描述算法的解题步骤，一般我们使用伪代码来具体描述算法步骤。例如下图：

其中<-代表赋值，while,do就是循环和具体的简单执行操作，当然你也可以加入注释来当做伪代码的一部分。我们一般在伪代码中忽略数据类型，变量的说明等于算法无关的部分。

算法分析–递归树和解递归

这里我们以归并排序的merge合并为例，假设现在要将两个数组进行merge归并，那么我们很容易想到每次都比较两个数组代插入新数组的数，每次都选择大的数插入，如下图：

竖着的代表一个数组，那么总体来看时间复杂度就是Θ(n)对于n个元素。这里我们列出递归式，归并排序每次都是将一个数组进行以2拆分，所以每次都会形成两个n/2元素的数组（这里就忽略不够n/2的过着看成n/2即可）那么我们刚刚说了merge时n个元素就是Θ(n)的复杂度，所以对于一个数组n进行拆分成了两个n/2的数组在merge就是T(n)=T(n/2)+T(n/2),再加上有限个步骤的指令所花费的时间Θ(n)，我们可以列出递归式：

$$T(n)=2T(n/2)+Θ(n)$$

展开递归树

那么接下来我们一般是根据递归式展开递归树，如下图

这是拆分两次后形成了4个n/4的子数组，然后需要一直拆分到T(1)，因为T(1)是一个具体的时间，所以最终T(n)用一个仅包含T(1)的式子表示就可以求出具体的时间复杂度了，如下我们继续展开递归树至T(1):

最终经过n此拆分，终于拆分结束发现树一共有log2n层一般表示为logn，那么我们最终进行估值，我们可以看出最后

$$cnlog2n<=T(n)<=cnlogn2n+O(n)$$

所以最终归并排序的时间复杂度为Θ(nlogn)这就是根据递归树求解时间复杂度渐进分析。

所以对于a和b的T(n)=aT(n/b)+cn，我们使用展开递归树时会得到下面的规律：

即对于T(n)=aT(n/ba)，最后我们会展开到h=logbn层，所以也就有a^h个叶子节点，所以就是n^logba个T(1)所以前项aT(n/b)就是Θ(n^logba)（其实这就是master最有力的理论证明)。

小练习

展开递归树求解T(n)=T(0.1n)+T(0.9n)+Θ(n)：

但是我们会发现展开递归树太难了，一步步展开递归树太反人类了，所以就有了解递归求解。

解递归–迭代展开

实际上展开递归树的过程就是迭代展开的过程，我们可以用公式来求解，如下：

我们求解T(n)=4T(n/2)+n

T(n)=4T(n/2)+n
=4(4T(n/2^2)+n/2)+n
=42T(n/2^2)+n+2n
=43T(n/2^3)+n+2n+2^2n
=4hT(n/2^h)+n(1+2+┅+2^h-1)
=n^2T(1)+n(2^h-1)
=Θ(n^2)

很多的递归式用递归解不出来我们可以使用递归式迭代展开求解，其实主要重点就是后面逐渐增大的等比数列求和以及总结归纳层数即次数问题，这里寻找层数h可以通过递归树来寻找规律。

思考：有没有一种较为特殊的系数递归式规律？

我们思考对于常数a,b的递归式T(n)=aT(n/b)+cn，拿到对于每次的a和b我们都一次次画递归树展开然后在迭代解递归求解？那计算量未免也太大了，我们试图寻找一种一劳永逸的解决结论，例如现在我们就对这个递归式进行迭代展开，对于a和b的具体数值我们不感兴趣。

那么T(n)=a^hT(1)+cn(1+(a/b)+…+(a/b)^h-1)= a^hT(1)+cb^h(1+(a/b)+…+(a/b)^h-1) ，此时对于b^h<n<b^h+1,仍然有h=Θ(logbn)即限界函数g(n)仍然受到参数b的影响，这里我们使用换底公式logbn=log2n/log2b，又因为log2b是一个常数对整体影响不大，所以我们知道h=Θ(logn),所以此时我们就总结出了以下结论又称为master定理：

递归式分析–Master定理

对于任意一个递归式T(n)=aT(n/b)+f(n），其中a>=1,b>=1且为整数，f(n)>0，我们总是有

aT(n/b)的时间复杂度为：

$$aT(n/b)=Θ(n^{log_ba})$$

又因为T(n)总是由最高次项所决定，所以T(n)主要是由n^logba和f(n)所决定。这里就会出现三种情形：

情形1

fn=O(n^(logba-ε))所以f(n)的增长会渐进地慢于n^logba,所以最终T(n)由前面一项所决定，所以T(n)=Θ(n^logba)。

情形2

fn=Θ(nlogba*(lgn)^k),即f(n)和n^logba几乎有相同的渐进增长率，所以T(n)=Θ(n^logba*(lgn)^k+1)。

情形3

fn=Ω(n^(logba+ε)),即f(n)多项式会逐渐地快于n^logba，则T(n)由后一项决定，所以T(n)=Θ(f(n))。

小练习

那么我们在用master定理求解以下几个式子：

T(n)=4T(n/2)+n,所以4T(n/2)=Θ(n^2),而f(n)=n慢，所以T(n)=Θ(n^2)。

T(n)=4T(n/2)+n^2,此时f(n)/n^2=1=(logn)^0,所以k=0,所以T(n)=Θ(n^2logn)(一定要注意这里是(logn)^k+1)。

T(n)=4T(n/2)+n^3,f(n)更大，所以T(n)=Θ(n^3)。

总结

其实这篇文章最后整理就是因为其最难理解，往往概念性的东西最难理解，例如时间复杂度的分析，对于递归树展开，递归式得迭代展开和master定理得使用要熟练掌握，如果学有余力，最好了解一下证明过程这样也有助于记住结论，那么希望你能有所收获😝。