分治法

顾名思义，分治法是将一块完整的领土分解为若干小的领土，然后一块块征服。

• 分，把一个问题的实例划分为若干个子问题（原问题规模变小）
• 治，递归地解决每个子问题
• 把每一个子问题的解整合为一个大问题的解

举例

归并排序（Merge sort）

• 将待排序的数组一分为二
• 递归地对每一个子数组排序
• 合并两个有序的子数组为一个有序的数组（在线性时间n内）

归并排序可以用a=2,b=2,k=0的主方法求解

二分查找方法（Binary search）

算法描述：设某个元素为x，需要在一个已经排序的数组中找到这个x。

• 分，把x与数组中间的元素比较
• 治，如果x小于中间元素，取前一半数组，否则取后一半，每次只在一个数组递归
• 合并，无计算量

乘方问题（Powering a number）

算法描述：给出一个数$a$a（实数或者浮点数）和正整数$n$n，计算$a^n$an。
传统的Naive算法直接按照$a^n$an的定义，$n$n个$a$a连乘计算，算法复杂度为$\Theta(n)$Θ(n)。
利用分治法：

• 分
  • 当$n$n为偶数，将$n$n分为$n/2$n/2，即$a^n=a^{n/2}a^{n/2}$an=an/2an/2，两个$a^{n/2}$an/2只要算一个就可以，所以子规模的规模变为$n/2$n/2。
  • 当$n$n为奇数，将$n$n分为$n/2$n/2，即$a^n=a^{n-1/2}a^{n-1/2}a$an=an−1/2an−1/2a，两个$a^{n-1/2}$an−1/2只要算一个就可以，所以子规模的规模变为$n/2$n/2。
• 治，类似二分查找，只要在一部分递归即可
• 合并

斐波那契数（Fibonacci numbers）

传统的Naive算法

传统的Naive算法按照定义向前逐步递归。

朴素平方递归式

斐波那契数列特性之一：$\phi^n/\sqrt{5}$ϕn/5​取最近的整数就是第n个斐波那契数。即$F(n)=[\phi^n/\sqrt{5}]$F(n)=[ϕn/5​]，此时斐波那契数列变成了乘方问题。算法复杂度为$\Theta(lgn)$Θ(lgn)。

此算法的问题在于，在计算的储存中，用浮点数储存$\phi$ϕ和$\sqrt{5}$5​，因此会影响到结果。
真正的平方递归式
利用特性同样能将斐波那契问题转化为乘方问题。算法复杂度为$\Theta(lgn)$Θ(lgn)。

矩阵乘法（Matrix multiplication）

朴素算法

朴素算法复杂度$\Theta(n^3)$Θ(n3)

分治法

• 分，矩阵分块，如图，分为8块
• 治，递归每一个子矩阵
• 合并，将子矩阵合并
  

矩阵分为8个子矩阵，规模变为$n/2$n/2，合并的时间为矩阵相加的算法复杂度为$\Theta(n^2)$Θ(n2)，最终的复杂度为$\Theta(n^3)$Θ(n3)，并没有更优。

分治法 Strassen’s idea

分析思路：我们不在乎矩阵加法的算法复杂度（$n^2$n2是可以接受的），算法优化应该从分块迭代部分考虑（减少乘法的次数）。

利用主方法的Case1情况求解，算法复杂度为$T(n) = \Theta(n^{lg 7})$T(n)=Θ(nlg7)，比原来的$\Theta(n^3)$Θ(n3)大大优化（特别是在n较大的情况下效果显著）。

超大规模集成电路（VLSI layout）

假设电路是个二叉树，现在有个n个叶结点的完全二叉树，算法目的在于找到网格占空间最小的方法。

改变布局，充分利用空白区域。