<span>分治算法</span>

一、算法设计与分析的基本概念

一、算法

算法是指解决问题的一种方法或一个过程。是若干指令的有穷序列。算法具有5个重要特性：

• (1)有穷性：算法必须在执行有穷步之后结束，且每一步都可以在有穷的时间内完成。
• (2)确定性：算法的每条指令必须有确切的含义，无歧义的。
• (3)可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
• (4)输入：一个算法有0个或多个输入。
• (5)输出：一个算法有1个或多个输出。

算法与程序的区别：

• 算法是解决问题的方法、步骤；
• 程序是算法的具体代码实现；
• 算法是程序设计的核心，算法的好坏直接决定了程序的效率。

二、算法设计

常用的算法设计技术：

    分治法     动态规划法    贪心法     回溯法     分支限界法

三、算法的表示

    自然语言     流程图     程序设计语言     伪代码

二、算法分析基础

一、算法复杂度分析

算法复杂度 = 算法所需要的计算机资源

• 算法的时间复杂度T(n)；
• 算法的空间复杂度S(n)。
  其中n是问题的规模（输入大小）。

1.空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。

temp=a; 
a=b; 
b=temp; 
空间复杂度为O(1)

2.时间复杂度

例1:    sum=0； 
for(i=0;i<n;i++)       
sum++； 

上面代码中第一行频度1，第二行频度为n，第三行频度为n，所以f(n)=1+n+n=2n+1。所以时间复杂度O(n)。即算法中操作次数和 n正比线性增长。

例2:    sum=0； 
for(i=0;i<n;i++)  
for(j=0;j<n;j++) 
sum++； 

第一行频度1，第二行n，第三行n²，第四行n²， T(n)=1+n+n2+n2=2n²+n+1 =O(n²)

例3:  int i=1; 
while (i<=n) 
i=i*2; 

2的f(n)次方<=n； f(n)<=log₂n，取最大值f(n)= log₂n， 所以T(n)=O(log₂n )

时间复杂度按从小到大排序： 常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n²)、立方阶O(n³)…

• （1）最坏情况下的时间复杂性
• （2）最好情况下的时间复杂性
• （3）平均情况下的时间复杂性

三、分治法

一、递归的概念

直接或间接地调用自身的算法称为递归算法。

递归两个要素： 
    边界条件，即确定递归到何时终止，也称为递归出口。 
    递归模式，即大问题如何分解成小问题，也称为递归体。

二、分治法的基本思想

分治法就是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法在每一层递归上都有三个步骤：

• 分解：将原问题分解为若干个小的、相互独立的、与原问题相同的子问题；
• 求解：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
• 合并：将各个子问题的解合并为原问题的解。

如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划法更好。

例：归并排序（从小到大排序）

归并排序算***把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。

首先，要把序列对半分割。

先分成两段……

再继续往下分……

分割完毕。接下来对分割后的元素进行合并。

把6和4合并，合并后的顺序为[4, 6]。

接下来把3和7合并，合并后的顺序为[3, 7]。

下面，我们来看看怎么合并 [4, 6]和[3, 7]。 合并这种含有多个数字的子序列时，要先比较首位数字，再移动较小的数字。

由于4＞3，所以移动3。

同样地，再次比较序列中剩下的首位数字。

由于4＜7，所以移动4。

由于6＜7，所以移动6。

最后移动剩下的7。

递归执行上面的操作，直到所有的数字都合为一个整体为止。

这里也要比较两个子序列中的首位数字。

由于3＞1，所以移动1。继续操作……

合并完成，序列的排序也就完成了。

归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分 割好的）。在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较 小的数据，因此只需花费和两个子序列的长度相应的运行时间。也就是说，完成一行归 并所需的运行时间取决于这一行的数据量。
看一下上面的图便能得知，无论哪一行都是 n 个数据，所以每行的运行时间都为 O( n)。 而将长度为 n 的序列对半分割直到只有一个数据为止时，可以分成 log2n 行，因此，总共有 log2n 行。也就是说，总的运行时间为 O(nlogn)，这与前面讲到的堆排序相同。