2019-11-17

Divide-and-Conquer

递归分治算法（1）

孙子兵法有云：“十则围之，五则攻之，倍则分之，敌则能战之，不若则能避之”，这句话的意思是说，十倍的兵力就合围；五倍的兵力就强攻；两倍的兵力就分散敌人，逐个击破；能打就打，不能打就跑——在不同的兵力下，有不同的应对策略。将兵法应用于编程：当计算能力足够的情况下，我们可以采取暴力的方法求解问题，但是当计算能力不足的时候，我们应该将问题分割，逐个求解，这也就是分治的思想。但是“Divide and rule, a sound motto,. Unite and lead, a better one”，翻译过来就是：分而治之是至理名言，和而御之却更显明智。分治算法的难点并不在于分而在于和，分的策略可能有很多种，但是如果分完后不能合起来那就是失败的。

如何分？

分治算法首先讲求一个“分”字，那么该如何来分呢？其实分是没有固定标准的，但是采用的“分法”必需能够“合”起来，下面给出几条经验总结：

根据问题的特点，通过恰当的分法使事物的规模降低或将问题分为若干小问题。这一点实际上在程序中随处可见，不仅仅是算法，我们将程序模块化，抽象出函数，采用面向对象的编程思维都是一种分的体现。切记如果问题在分解后没有得到简化反而复杂化了，那么这种分法是不可取的。
在分解问题时尽量去靠近已经解决的问题。如果一个问题如果通过某种分解方法可以得到几个子问题，而这几个子问题已经有很好的解决方法或者通过简单的变换可以转换为已经解决的问题，那么原问题就能得到很好的解决。
找到递归的模式。有时候一个问题分一次可能并不能解决问题，但是如果分得的子问题具有与原问题具有一样的形式只是规模缩小了，那么我们继续分割子问题就可以达到这个问题的最小子问题，而这个最小子问题能够很好的被解决，那么我们就可以递归的解决问题。

怎么和？

如果是分为若干子问题，那么求解出这些子问题原问题就得到了解决；如果采用递归的方法，那么我们就需要找到子问题与它的父问题的联系，逐层递归最终得到原问题的解。怎么和是很难用言语概况的，针对不同的问题，和的方法都不尽相同。下面我希望通过经典的排序问题对“怎么合”这个问题给出一个解答。

分治算法的经典例子——排序

传统的排序算法（暴力法）常见的有冒泡排序和选择排序，但是无论哪种排序都使用了双重循环，也就是说他们的复杂的都为$O(n^{2})$，这个复杂的已经算很高了，在如今大数据的时代，可能一个库里有上亿的数据量，这个时候传统排序耗费的时间太长，也就是目前的计算能力还开销不起，因此提高排序算法的效率是十分必要的。改进的排序算法有很多种，但是几乎都采用了分治的策略，下面我们以其中两种为例进行分析：

快速排序

快排是一种典型的白盒划分的分治算法，采用分治策略将算法复杂度下限降低到了$O(nlogn)$，相比暴力法效率有较大的提升。

快排的基本思想：

“分”的策略：快排在分的时候以某个元素为基准把待排序的数组分成两堆，一堆大于基准，一堆小于基准。为了编程的方便，我们一般选取数组的第一个元素为基准，将大于第一个元素的放到一堆，小于第一个元素的放到另一边。这样原来的数组被划分为两部分（基准可以任选，取决于程序的编写）。
“和”的策略：在这个问题中，分一次显然无法得到问题的答案，但是分完后这两堆相比于原来的数组规模降低了但任保留了原问题的形式，即任是一个排序问题，只是排序的规模下降了，所以我们可以按照上面的分法继续分下去，当分到只有两个元素成一堆时就是原问题的最小子问题，这个时候我们只要比较大小交换位置就可以使最小子问题解决，由于此分法的特点，我们可以发现当所有的最小子问题解决后原问题就解决了——因为在划分的时候就保证了子问题之间是按序从小到大的，所以这里没有涉及“和”的问题。因此分治算法不一定会有“和”的过程，此算法就是一个例子。

下面是快速排序一个例子的图解，结合图可以更好地理解上述的基本思想，图中灰色元素为基准元素。

mark

快排的代码实现：

 //此程序选取数组第一个元素作为基准
public static void QuickRank(int[] list, int start, int end)
        {
     		//退出递归的条件
            if (end - start < 1) return;
            int middle = 0;
            int i = start + 1;
    		//从后往前搜索一个比基准元素小的元素
            for (int j = end; j >= start; j--)
            {
                //退出搜索的条件，原来就有序的情况
                if (j < i) break;
                //将第一个判断分完堆后交界元素与基准元素大小关系，据此确定基准元素的位置，将基准元素与该位置元素交换
                if (i == j)
                {
                    if (list[i] < list[start])
                    {
                        int temp;
                        temp = list[start];
                        list[start] = list[i];
                        list[i] = temp;
                        middle = i;
                    }
                    else
                    {
                        int temp;
                        temp = list[start];
                        list[start] = list[i - 1];
                        list[i - 1] = temp;
                        middle = i - 1;
                    }

                    break;
                }
				//找到比基准元素小的元素后从前往后找到一个比基准元素大的元素，与之前找到的元素交换
                if (list[j] < list[start])
                {
                    for (; i <= end; i++)
                    {
                        if (i == j)
                        {
                            if (list[i] < list[start])
                            {
                                int temp;
                                temp = list[start];
                                list[start] = list[i];
                                list[i] = temp;
                                middle = i;
                            }
                            else
                            {
                                int temp;
                                temp = list[start];
                                list[start] = list[i - 1];
                                list[i - 1] = temp;
                                middle = i - 1;
                            }
                            break;
                        }
                        if (list[i] > list[start])
                        {
                            int temp;
                            temp = list[j];
                            list[j] = list[i];
                            list[i] = temp;
                            break;
                        }
                    }
                }

            }
    		//递归调用
            QuickRank(list, start, middle);
            QuickRank(list, middle + 1, end);

        }
    }
}

快排算法复杂度的分析：

前面提到算法复杂度的下限是$nlogn$，这意味着通常情况下，快排的复杂度是大于$nlogn$的。复杂度下限的取得条件是：每次都能分成大小相等的两堆，此时有递推关系$QuickRank(n)=2*QuickRank(n-1)$，解此递推式可以得到下限$O(nlogn)$；但是当每次分成的两堆大小相差比较大时，比如一堆分得一个，另一堆分得剩下的全部，那么我们可以得到递推式$QuickRank(n)=QuickRank(n-1)+QuickRank(1)+O(n)$，解此递推关系可以发现复杂度为$O(n^{2})$，这是最差的情况，一般快排复杂度介于两者之间。

合并排序

合并排序是一种典型的白盒划分的分治算法，它的时间复杂度为$O(nlogn)$，比暴力法和快排的效率都要高。

合并排序的基本思想：

“分”的策略：合并排序在分的时候一刀两断，将数组分成大小相等的两堆（元素个数为奇数时不能平分，但基本上是平分的），然后递归调用函数，继续分，直到分解到两个元素（或一个元素）为一堆的时候，此时比较两个元素，交换位置就能得到最小子问题的解。
“和”的策略：与快排不同的是，合并排序采用了黑盒划分的方法，因此无法保证最小子问题的解放到一起还是升序的，所以就有合的步骤。此处“合”需要解决的问题是：将两个升序的数组合并为一个升序的数组，解决这个问题可以采用逐次比较的方法（需要额外申请内存空间，用于存放合并的结果）——首先让两个指针指向两个数组的首位元素，通过指针比较两个数组首元素的大小，将小的元素放到结果数组中，然后此元素对应的指针+1；继续通过这两个指针比较当前指向的两个元素的大小，重复上述操作直到其中一个指针到底对应数组的末尾，将未到达末尾的指针对应的数组中未比较的元素拷贝到结果数组中，至此合并完成。

下面是合并排序一个例子的图解，图中只给出了“分”的具体过程，结合图可以更好地理解上述的基本思想。

mark

合并排序的实现：

void Merge_sort(int* list, int low, int up)
{
	if (low == up)return;
	int middle = (low + up) / 2;
	int size = up - low + 1;
	int* temp = (int*)malloc(sizeof(int)*size);
    //递归调用
	Merge_sort(list, low, middle);
	Merge_sort(list, middle + 1, up);
	Merge(list, low, up, temp);
	list = list + low;
    //将结果拷贝回原来的数组
	while (size-->0)
	{
		*list++ = *temp++;
	}
}

void Merge(int*list, int start, int end, int*temp)
{
	int* left = list+start;
	int middleNum = (end + start) / 2;
	int* right = list +middleNum+1;
	int* endPoint = list + end;
    //逐次比较
	while (left <= list + middleNum && right <= endPoint)
	{
		if(*(left) < *(right))
		{
			*temp++ = *(left++);
		}
		else
		{
			*(temp++) = *(right++);
		}
	}
    //找到未经比较的元素，拷贝到结果数组
	if (left <= list + middleNum) {
		while (left <= list + middleNum)
		{
			*temp++ = *left++;
		}
	}
	else
	{
		while (right <= endPoint)
		{
			*temp++ = *right++;
		}
	}
	
}

快排算法复杂度的分析：

前面提到算法复杂度为$O(nlogn)$，这意味着不管在什么情况下，合并排序的复杂度都为$O(nlogn)$。这是因为合并排序每次都能分成大小相等的两堆，递推关系始终满足关系式$QuickRank(n)=2*QuickRank(n-1)$，因此复杂度始终为$O(nlogn)$。

两种排序算法的比较

合并排序的性能要比快速排序高，这取决于“分”的策略不同，所以对于分治算法来说如何“分”决定着算法的性能。这两个排序算法还涉及到黑盒划分和白盒划分的区别——所谓黑盒划分就是按照某种规则划分后无法得知划分的情况（输入未知的情况下）；而白盒划分则是按照某种规则划分后我们可以得知划分的情况。拿合并排序和快速排序来讲，采用合并排序时每次对半划分，但是我们无法知道最后每个最小子问题之间有什么关系，但是采用快速排序时根据基准，我们可以知道最小子问题是有序的，或者说对于其中一次划分，我们可以肯定：划分出的两堆数，其中一堆的数都大于另一堆。实质上白盒划分和黑盒划分的区别在于白盒划分降低了划分结果的不确定性，即对划分结果做出了某些限定，在合并排序中相当于限定了划分结果的大小关系。

本文标题:Divide-and-Conquer

文章作者:ZhuMing

发布时间:2019-11-17, 12:51:58

最后更新:2019-11-17, 12:52:00

原始链接:http://zhumingcj.github.io/2019/11/17/divide-and-conquer/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。