分治策略求解递归式之主方法

前言：

在之前的文章中笔者介绍了归并排序，归并排序的核心思想就是分治，引出了这次笔者关于分治策略的介绍。

正文：

正如在归并排序中提及的，分治策略中求解问题采用递归的方法，每层递归分为三个步骤：

• 分解，将问题划分为规模更小的子问题。
• 解决，递归求解出小问题，当小问题规模足够小时，停止递归，直接求解。
• 合并，将小问题的解合并成原问题的解。

当子问题足够大时，需要继续递归求解，称之为递归情况。

而当子问题规模足够小时，不需要继续递归，可以进行求解，称之为基本情况。

注意，有时需要求解与原问题不完全一样的子问题，将其求解看做合并步骤的一部分。

求解递归式的方法有三个：

• 代入法：猜测一个界，然后用数学归纳法证明这个界是正确的。
• 递归树法：将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。采用边界和技术来求解递归式。
• 主方法：可求解形如下面公式的递归式的界。

T(n)=aT(n/b)+f(n)

其中a>=1,b>1,f(n)是一个给定的函数。它刻画了这样一个分治算法，生成a个子问题，每个子问题是原问题规模的1/b，分解和合并步骤花费时间为f(n)。

递归式细节

在实际应用中常常会忽略递归式声明和一些技术细节，比如向下取整、向上取整以及边界条件。

例如，对n个数进行归并排序，当n为奇数时，两个子问题的规模精确来说不是n/2而应该分别是，n/2的向下取整与向上取整。而在实际运算和描述其最坏情况运算时间时，我们都忽略了这个细节而直接取n/2进行讨论。

实例分析：最大子数组问题（参考自算法导论）

你初次接触股票看中了一家生物化学公司，而这家公司股票价格不算稳定。你可以在某个时刻买进一股该公司的股票，并在之后的某天卖出，假设你获得了这家公司未来的价格走向，但是你进行买进卖出都只能在当天交易结束后进行。用表格的形式展示价格走向：

天数	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
价格	100	113	110	85	105	102	86	63	81	101	94	106	101	79	94	90	97
差价	13	-3	-25	20	-3	-16	-23	18	20	-7	12	-5	-22	15	-4	7

由此可见实际所求即为求一个最大子数组的问题。

采用分治策略，把原数组分为两个规模尽可能相等的子数组。

而对于最大子数组只会出现两种情况：1、完全位于子数组中；2、跨越中点。

具体的代码实现可参考一下两篇文章：

最大子数组递归和非递归(暴力)

最大子数组问题（动态规划）–【算法导论】

在这里提一下，笔者正在尝试在Github上建立自己的博客，当然是从参考别人的博客开始一步步慢慢来，当有所成果之后会提供链接，欢迎大家去看。