算法基础+分治策略（算法复习第1弹）

马上就要算法考试了，好紧张，先复习第一波....

参考文献（算法导论）+（张莉老师ppt）

函数的增长，对算法效率的描述

渐进记号：Θ、Ω、O、o、w(那个很像w的符号，不记得咋打出来了)

Θ标记（最常用）：存在正常量c1和c2，使得当n 足够大的时候，能够让函数 f(n) 夹入c1g(n)和c2g(n)之间

如图：

f(n）=Θ（g(n)) 图一

称g(n)是f(n）的一个渐进紧确界，也就是f(n）得在c1g(n)和c2g(n)之间，不得越界

举个例子证明（考点)：

证明这个式子

图二

Ω标记：渐进下界

如图，和图一相比，它没有上界要求，图一上下均不能越界，它只有下界要求，所以叫做渐近下界

图三

O：渐近上界

和Ω标记类似，上边不越界，下边不做要求

图四

o标记：非渐进紧确的上界，图一Θ是渐进紧确的，而O可以是Θ

也可以不是，而o有点像集合中真包含的概念，它不是Θ的O

w(那个很像w的符号，不记得咋打出来了)标记符：和o相反，非渐进紧确的下界

通过上边几个图的理解，下边表里边的式子就很好理解了

左边是满足的表达式，右边是两者的相对增长速度

图五

这也是比较两个函数之间增长速度的方法（n足够大的时候，求函数之比的极限，根据结果判断）

图六

分治策略

概念：将原问题分解成子问题，子问题与原问题一样，至少规模更小，直到规模足够小，递归停止，问题得以解决

包括的例子有，归并排序、实验中的gray码问题

分治算法的分析：

分治法解题的一般步骤

（1）分解，将要解决的问题划分成若干规模较小的同类问题；

（2）求解，当子问题划分得足够小时，用较简单的方法解决；

（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

三个求解分治法Θ或Ω的方法

1、代入法

即假设一个界，然后数学归纳法证明

这种方法需要经验的积累，可以通过转换为先前见过的类似递归式来求解。

2、递归树法

在递归树中，每一个结点都代表递归函数调用集合中一个子问题的代价。将递归树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。

如归并排序，忘了归并排序的可以参照这里  归并排序

这是其递归式

图七

这是递归树的式子（主方法常用这个式子）

图八

递归树式子需要解释的地方有

cn其实就是一个函数f(n),这个函数所代表的意思是分解和合并步骤所花费的时间，哈哈

其（f(n)）复杂度为Θ（n）,由此再去理解图七中的式子就好理解了

下面来用递归树的方法求分治算法的渐进界：

下边这是ppt上的例子，怎么理解这个递归树例子呢，最顶层是cn,从它开始递归，首先你可以把n理解为2的某次幂，比如，n是2的4次幂，所以整个递归树就有(logn)也就是4层，每一层的代价刚好都是cn，可求出其T（n）,第5层也就是常量的，为Θ（n），也可以回去图八和图七解释，哈哈

图九

这个例子也一样，只不过不是递归成一样的问题，是两个一样的子问题

图十

3、主方法法

它可以瞬间估计一个递推式的算法复杂度。但是我们知道，这后面肯定是严格的数学证明在支撑着，对于我们用户来说，我们只用知道怎么用就行了。

T(n) = aT(n/b) + f (n) ,函数f(n),这个函数所代表的意思是分解和合并步骤所花费的时间

下图就是主定理，记住就行，也可以自己去推导一蛤~

图十一

PPT上这样说主定理，一样的

图十二

图十三

下面贴一段gray码问题的分治解法

图十四

第一次写简书，写的乱乱的，明天将推出动态规划和毛概，希望写的更好，祝大家期末取得好成绩~