文章插图
算法一：分治法
基本概念
1.把一个复杂的问题分成两个或更多的相同或相似的子问题 ， 再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解 ， 原问题的解即子问题的解的合并 。
2.分治策略是对于一个规模为n的问题 ， 若该问题可以容易地解决（比如说规模n较小）则直接解决 ， 否则将其分解为k个规模较小的子问题 ， 这些子问题互相独立且与原问题形式相同 ， 递归地解这些子问题 ， 然后将各子问题的解合并得到原问题的解 。
适用情况
1)该问题的规模缩小到一定的程度就可以容易地解决
2)该问题可以分解为若干个规模较小的相同问题 ， 即该问题具有最优子结构性质 。
3)利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的 ， 即子问题之间不包含公共的子子问题 。
分治法的复杂性分析
一个分治法将规模为n的问题分成k个规模为n／m的子问题去解 。设分解阀值n0=1 ， 且adhoc解规模为1的问题耗费1个单位时间 。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间 。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间 ， 则有：
T（n）= k T(n/m)+f(n)
通过迭代法求得方程的解：
递归方程及其解只给出n等于m的方幂时T(n)的值 ， 但是如果认为T(n)足够平滑 ， 那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度 。通常假定T(n)是单调上升的 ， 从而当 mi≤n<mi+1时 ， T(mi)≤T(n)<T(mi+1) 。
分治法例题：合并排序和快速排序
public class 分治_合并排序 {
/**
* 函数说明：在数组被拆分以后进行合并
*/
static void Merge(int a[], int left, int middle, int rigth) {
//定义左端数组大小
int n1 = middle - left+1;
int n2 = rigth - middle;
//初始化数组 ， 分配内存
int bejin[] = new int[n1];
int end[] = new int[n2];
//数组赋值
for(int i = 0; i < n1; i++)
bejin[i] = a[left + i];
for(int i = 0; i < n2; i++)
end[i] = a[middle+1+i];
//用key做原数组索引 ， 没调用一次函数重新给原数组付一次值
int i = 0, j = 0, key;
for(key = left; key <= rigth; key++){
if(n1>i&&n2>j&&i < n1 && bejin[i] <= end[j])
a[key] = bejin[i++];
else if(n1>i&&n2>j&&j < n2 && bejin[i] >= end[j])
a[key] = end[j++];
else if(i == n1 && j < n2)
a[key] = end[j++];
else if(j == n2 && i < n1)
a[key] = bejin[i++];
}
}
/**
* 差分数组区间 ， 不断分支
*/
static void MergeSort(int a[],int left,int rigth) {
int middle=0;
if(left<rigth) {
middle =(rigth+left)/2;
MergeSort(a, left, middle);
MergeSort(a, middle+1, rigth);
Merge(a, left, middle, rigth);
}
}
public static void main(String[] args) {
int a[]= {85,3,52,9,7,1,5,4};
MergeSort(a, 0,7);
for(int i=0;i<8;i++) {
System.out.print(" "+a[i]);
}
}
}
public class 分治_快速排序 {
/**
*交换函数 ， i ， j为数组索引
*/
static void swap(int A[], int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
/**
* 选取一个关键字(key)作为枢轴 ， 一般取整组记录的第一个数/最后一个 ， 这里采用选取序列最后一个数为枢轴 。
* 设置两个变量left = 0;right = N - 1;
* 从left一直向后走 ， 直到找到一个大于key的值 ， right从后至前 ， 直至找到一个小于key的值 ， 然后交换这两个数 。
* 重复第三步 ， 一直往后找 ， 直到left和right相遇 ， 这时将key放置left的位置即可 。
* @return
*/
static int PartSort(int[] array,int left,int right)
{
int key = array[right];//定义基准
int count=right;//保存rigth值
while(left < right)//防止数组越界
{
while(left < right && array[left] <= key)
{
++left;
}
while(left < right && array[right] >= key)
{
推荐阅读
- 简谈企业最常用的三种安卓app开发语言
- 解开“肺功能”检查五大疑惑
- 八大常用茶叶贮存方法简介
- 你必需知道的10个 Nginx 常用命令
- mysql之my.cnf/my.ini常用配置整理
- JAVA手写tomcat，带你了解tomcat的原理，附代码
- 普洱茶选购要掌握五大原则
- 茶叶产品4大常用有效贮存方法
- 中国古代五大酷刑是什么 中国古代最残酷的刑
- 简单了解Java消息队列