分治策略与递归

最新推荐文章于 2022-11-08 15:52:56 发布

cxy4562

最新推荐文章于 2022-11-08 15:52:56 发布

阅读量840

点赞数

分类专栏：数据结构文章标签：分治策略递归数据结构

本文链接：https://blog.csdn.net/cxy4562/article/details/39104101

版权

数据结构专栏收录该内容

1 篇文章

订阅专栏

本文探讨了分治策略的核心要素——划分、递归和合并，并强调理解递归的关键在于基准情形、不断推进、设计法则和合成效益法则。通过分析最大子列和问题，展示了如何运用分治策略提高效率。然而，实际代码实现中，递归的逻辑复杂性成为理解难点，需要更多实践来深化理解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

先看《数据结构与算法分析》中对分治策略的解释：把问题分成两个大致相等的子问题，然后再递归地对他们进行求解，这是“分”。“治”阶段将两个子问题的解合并到一起并可能再做些少量的附加工作，最后得到整个问题的解。

由定义可以看出，分治需要进行两步操作："分"-->将问题恰当的划分为需要迭代处理的两个子问题，“治”-->将两个子问题合并。关键的操作有三点：

1、如何划分？即以怎样的准则对整体进行划分

2、如何递归？即设计怎样的递归方式

3、如何合并？即用怎样的方式将整个问题还原

划分的准则和整个问题的还原方法千千万，应该具体问题具体分析，而递归是存在一些设计准则的：

1、基准情形。即递归的终止条件，其必须不依赖递归就能解出。

2、不断推进。每一次递归都必须使得求解情况向基准情形靠近。

3、设计法则。假设所有的递归调用都能够运行，即不会出现这次递归成功，而下次失败（没有达到基准情形）的情况。从头至尾都是进行同样的操作，并且都不会出错。

4、合成效益法则。求解同一个问题的同一个实例时，不要在不同的递归调用中作重复性的工作。意即在当前递归中计算出的数据，不应当在下次递归中在进行相同的计算。

即使有了上述准则，对递归还是难以理解。具体表现为：原理感觉理解的很清楚，但是很难用代码来实现。目前还没有发现什么好的解决方法，只能寄希望于通过大量的实践操作来理解。

下面是书上的一个例子，感觉很不错，拿过来分析一下：

要求：给定一个整型数序列，求出它的最大子列和（子列是连续的）。

分析：求最大子列和，常规的方法就是用两层循环，遍历所有的子列组合，找出其中的最大值，这样的方法的运行时间为O(N^2)，效率有些偏低，用“分治”策略来解决会有更高的效率。

分治策略分析：最大子列存在三种情况，如下图所示

以center为基准线，则最大子列和有三种情形：基准线的左边、基准线的右边、包含基准线。以此类推，左右两边有可以划分为更小的以这种方式划分的序列，直到基准情形出现——只有一个值（left==right=center），这样就形成了一个递归的形式。最后还需要有一个对三者的比较操作，从而将问题合并，找出最大子列和。下面是c语言的实现函数代码：

//“分治“策略求解问题【子问题运用递归解决】
int MaxSubsequenceSum_2(int a[], int left, int right)
{
	int MaxLeftSum, MaxRightSum;
	int MaxLeftBorderSum, MaxRightBorderSum;
	int LeftBorderSum, RightBorderSum;
	int center, i;
	//【基准情形】
	if(left == right)
	{
		if(a[left] > 0)
			return a[left];
		else
			return 0;
	}

	center = (left+right)/2;
	MaxLeftSum = MaxSubsequenceSum_2(a, left, center);//【递归得到左边的最大子列和】
	MaxRightSum = MaxSubsequenceSum_2(a, center+1, right);//【递归得到右边的最大子列和】

	MaxLeftBorderSum = 0;					//【下面计算包含中间值的最大子列和】
	LeftBorderSum = 0;					//【可以看出分成了三个部分，两部分用来迭代】
	for(i=center; i>=left; i--)				//【递归确实很难理解，多思考吧】
	{
		LeftBorderSum += a[i];
		if(LeftBorderSum > MaxLeftBorderSum)
			MaxLeftBorderSum = LeftBorderSum;
	}

	MaxRightBorderSum = 0;
	RightBorderSum = 0;
	for(i=center+1; i<=right; i++)
	{
		RightBorderSum += a[i];
		if(RightBorderSum > MaxRightBorderSum)
			MaxRightBorderSum = RightBorderSum;
	}

	if(MaxLeftSum >= MaxRightSum)
	{
		if(MaxLeftSum >= (MaxLeftBorderSum+MaxRightBorderSum))
			return MaxLeftSum;
		else
			return MaxLeftBorderSum+MaxRightBorderSum;
	}
	else
	{
		if(MaxRightSum >= (MaxLeftBorderSum+MaxRightBorderSum))
			return MaxRightSum;
		else
			return MaxLeftBorderSum+MaxRightBorderSum;
	}

}

其实对这个程序，我还是有一些疑惑的，当debug的时候，编译器对递归的处理操作有些难以让人理解。尤其是两行递归代码（MaxLeftSum和MaxRightSum代码）的后面，紧跟的是计算从基准线开始向两边行进的最大子列和，那么左右两边不包括基准线的最大子列和是如何实现的呢？debug发现递归的处理操作相较于循环的逻辑不是那么的清晰，甚至看起来有些复杂，然而它的运行时间反而是O(NlogN)，这应该说是我还没有真正理解递归的思想，逻辑不够清晰，下来要好好的琢磨。