概述
在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
分治策略
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治法适用的情况
分治法所能解决的问题一般具有以下几个特征：
- 该问题的规模缩小到一定的程度就可以容易地解决
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
- 利用该问题分解出的子问题的解可以合并为该问题的解；
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
分治法的基本步骤
分治法在每一层递归上都有三个步骤：
1.divide（分解）：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
2 conquer（求解）：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
3 Combine（组合）：将各个子问题的解合并为原问题的解。
image.png
如何给一堆数字排序？答：分成两半，先排左半边再排右半边，最后合并就行了，至于怎么排左边和右边，请重新阅读这句话。
void merge_sort(int array[], unsigned int first, unsigned int last)
{
int mid = 0;
if(first<last)
{
mid = (first+last)/2;
merge_sort(array, first, mid);
merge_sort(array, mid+1,last);
merge(array,first,mid,last);
}
}
在merge_sort()中，将原来针对索引first到last的数组排序的问题，分为二份较小的问题
先针对索引first到mid的数组排序。
再针对索引mid+1到last的数组排序。
最后再进行二个数组的合并。
算法举例
回文
这里的回文是指资格字符串，它从头到尾读与从尾到头读的内容是一致的，比如说doggod,无论从左到右耗时从右到左都是一样的。
def isPal(s):
if len(s) <= 1:
return True
else:
return s[0]==s[-1] and isPal(s[1:-1])
s = 'doggod'
result = isPal(s)
print result
二分查找
二分查找的思路比较简单：
1） 选择一个标志i将集合分为二个子集合
2） 判断标志L(i)是否能与要查找的值des相等，相等则直接返回
3） 否则判断L(i)与des的大小
4） 基于判断的结果决定下步是向左查找还是向右查找
5） 递归记性上面的步骤
def binarySearch(L,e,low,high):
if high == low:
return L[low] == e
mid = (low+high)//2
if L[mid]==e:
return True
elif L[mid]>e:
if low == mid:
return False
else:
return binarySearch(L,e,low, mid-1)
else:
return binarySearch(L,e,mid+1,high)
def search(L,e):
result = binarySearch(L,e,0,len(L)-1)
print result
L = range(10);
e = 7
search(L,e)
大整数乘法
图片.png
大整数从高位到低位，被平分成了两部分。设整数1的高位部分是A，低位部分是B；整数2的高位部分是C，低位部分是D，那么有如下等式：
image
如果把大整数的长度抽象为n，那么：
image
因此，整数1与整数2 的乘积可以写成下面的形式：
image
如此一来，原本长度为****n****的大整数的****1次****乘积，被转化成了长度为****n/2****的大整数的****4次****乘积（AC，AD，BC，BD）。
master theorem主定理
master定理的英语名称是master theorem，它为许多由分治法得到的递推关系式提供了渐进时间复杂度分析。
设常数a >= 1，b > 1，如果一个算法的整体计算规模 T(n) = a T(n / b) + f(n)，那么则有如下规律：
image.png
合并排序
v2-a29c0dd0186d1f8cef3c5ebdedf3e5a3_b.gif
1.如果给的数组只有一个元素的话，直接返回（也就是递归到最底层的一个情况）
2.把整个数组分为尽可能相等的两个部分（分）
3.对于两个被分开的两个部分进行整个归并排序（治）
4.把两个被分开且排好序的数组拼接在一起
image.png
def merge_sort(array):
if (len(array) <= 1):
return array
mid = int(len(array) / 2)
left = merge_sort(array[:mid])
right = merge_sort(array[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
#此处有i,j两个索引,当其中一边推入完成,另一边可直接将剩下的推入
result += left[i:]
result += right[j:]
return result
array = [5, 3, 2, 8, 6, 1, 4, 7]
print(merge_sort(array))
快速排序
quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if item <= array[0]]) + [array[0]] + quick_sort([item for item in array[1:] if item > array[0]])
1.选择基准值：在待排序列中，按照某种方式挑出一个元素，作为基准值。
2.分割操作：以该基准值在序列中的实际位置，把序列分成两个子序列，一边是比它大的值，另外一边是比它小的值。
3.递归：对两个子序列进行快排，直到序列为空或者只有一个元素。
ef quick_sort(arr):
"""快速排序"""
if len(arr) < 2:
return arr
# 选取基准，随便选哪个都可以，选中间的便于理解
mid = arr[len(arr) // 2]
# 定义基准值左右两个数列
left, right = [], []
# 从原始数组中移除基准值
arr.remove(mid)
for item in arr:
# 大于基准值放右边
if item >= mid:
right.append(item)
else:
# 小于基准值放左边
left.append(item)
# 使用迭代进行比较
return quick_sort(left) + [mid] + quick_sort(right)
Strassen矩阵乘法
棋盘覆盖
线性时间选择
最接近点对问题
循环赛日程表
汉诺塔
网友评论