1、什么是分而治之

分治算法图示

顾名思义，“分而治之”是一种策略，其中给定的问题被拆分为一组子问题。

然后单独处理/解决每个子问题。

一旦解决了所有子问题，我们就把这些子问题的子解结合起来，找到最终的解。

2、分而治之策略

分而治之大致是一个三步策略：

将实际问题划分为子问题（子问题只是同一问题的较小实例）。求解，即递归解决每个子问题。结合子问题的解决方案，得到实际问题的解决方案。3、分而治之的基本原理

关系公式

关系公式是为给定问题解决方案生成的公式。大问题的求解需要这个公式来应用分而治之，将问题分解为子问题，然后递归地解决它们。

停止条件

停止条件定义了需要停止将主要问题划分为子问题并开始组合从子问题中获得的结果的点。也可以说停止条件定义了递归算法的基本情况。

4、分而治之的优点分而治之算法递归解决所有问题，所以任何需要递归的问题都可以利用分而治之。河内塔是最大的数学难题之一。但是分而治之算法已经成功地递归地解决了它。分而治之将问题划分为可以同时并行运行的子问题。因此，该算法适用于并行性。这种分而治之的特性在操作系统中被广泛使用。分而治之策略利用了缓存，因为在递归中反复使用变量。在缓存中执行问题比主内存更快。蛮力技术与分而治之技术相似，但分而治之比蛮力法更精通。分而治之技术比其他算法快得多。5、分而治之的缺点分而治之技术使用递归。递归反过来又会导致大量的空间复杂性，因为它利用了堆栈。分而治之的实现需要高内存管理。显式堆栈可能会过度使用内存。如果递归执行不正确，系统可能会崩溃。6、分而治之 VS 动态规划

分而治之都利用递归来寻找问题的解决方案，但它们都具有不同的属性，因此问题集也不同。在分而治之和动态规划中，将给定的问题划分为多个子问题，然后解决这些子问题。在动态规划中，同样的问题需要一次又一次地解决。然而，在分而治之中，将问题分成单独的子问题，并计算一次。然后合并最终的结果。

例如，在归并排序算法中，我们使用了分而治之技术，这样就没有必要再次计算同一个子问题。

但是，当我们计算斐波那契数列时，我们需要一次又一次地计算过去两个数字的总和才能得到下一个数字。

这就是为什么求解斐波那契数列需要动态规划的原因。

借助归并排序和斐波那契级数来了解动态规划和分而治之算法的比较。

归并排序

基础数组 归并排序

斐波那契数列

Member=[ ];fibonacci(n){    if  n in Member        return member[n];    else{           if( n < 2) fib= 1;      else fib = fib(n - 1) + fib(n -2);    }    mem[n] = fib;    return fib;}

编写一个函数，使用分而治之方法生成斐波那契数列。

fibonacci(n){    If n < 2        return 1;    else         return fib(n - 1) + fib(n -2);}

分而治之的策略有多种应用领域，例如：

1.有缺陷的棋盘2. 二进制搜索3. 查找数组中的最大值和最小值4. 合并排序5. 快速排序6. 斯特拉森矩阵乘法查找数组中的最大值和最小值

蛮力法 or 迭代法

FindMax(A, n){  int i;  max = A[0];  for(i=1; i<n; i++){    If(A[i] > max)      max = A[i];  }  Return max;}

同理 findMin 逻辑相反即可

分而治之算法

伪代码描述

二叉排序树搜索

BSearch(A, i, j, x){  if(i == j){    if(A[i] == x)      return I;    else      return -1;  }  mid = (i + j)/2;if(A[mid] == x)    return mid;  else if(x < A[mid])    return BSearch(A, i, mid-i, x)  else    return Bsearch(A, mid+1, j, x)}

此算法的时间复杂度为 O（log n）。在这里，考虑以 2 为基数的对数。因此，可以说该搜索比简单的线性搜索算法更好。这是因为线性搜索的时间复杂度为 O（n），远高于二叉排序树搜索的复杂度。

快速排序

Algorithm QuickSort(p,q){    //Sort the elemnets a[p]....a[q] which reside in the     //global array a[1:n] into ascending order;     if(p<q){   //If there are more than 1 elemnets        //Divide p into sub-problems        j := partitionArray(a, p, q+1);            //j is the position of the partitioning element.        //Solve the sub-problems.        QuickSort(p, j-1);        QuickSort(j+1, q);    }}

快速排序 动画描述

总结

本文详细介绍了分而治之的方法以及这种策略的一些实际应用。本文还深入探讨了如何递归解决分而治之的问题。

喜欢的关注，转发，后续精彩内容不容错过，谢谢。

继续淦~~~~~~~~~