算法导论——分治策略

之前在排序的时候我们提到了归并排序，使用了分治法。实际上分治法的应用非常多，这篇文章主要介绍分治策略的分析以及一些使用分治策略的算法。 分治策略分为分解，解决，合并三个过程。一般来说分治策略非常自然的写法就是写成递归式。在分解成子问题时，如果子问题足够大还需要递归求解，我们称之为递归情况，当子问题足够小不能再分解，我们成为基本情况。有时候除了解决与原问题一样的规模更小的子问题外，还会解决与原问题不一样的子问题。 ### 递归式 ### 对于递归式我们并不陌生，如果需要写递归的算法就会有递归式。比如之前的归并排序，运行时间的递归式为： $$T(n) = 2T(n/2) + \Theta(n), n>1$$ 求解可得$T(n) = \Theta(n\text{lg} n)$。这里提三种求解递归式的方法，也就是从递归式得到算法$\Theta$或者$O$渐近界的方法： * 代入法。猜测一个界，用数学归纳法证明是正确的。 * 递归树法。将递归式转化成一棵树，其节点表示不同层次的递归调用产生的代价，采用边界和技术求解递归式。 * 主方法（主定理）。这个名字听起来很奇怪，但是是本篇文章的重点。只要递归式符合主方法的形式，那么它就可以轻易求解得出。主方法可求解形如下面公式的递归式： $$T(n) = aT(n/b) + f(n)$$ 其中$a\ge 1,b>1,f(n)$是一个给定的函数。这个形式刻画了一个分治策略：将原问题分解成$a$个规模为$n/b$的子问题，而分解合并这些子问题的步骤花费为$f(n)$。

有时候我们也会遇到不等式的递归式，如$T(n)\leq 2T(n/2) + \Theta(n)$，那么这个递归式给出了上界，我们使用$O$来描述求解出来的渐近界。如果给出了下界，则对应的使用$\Omega$来描述渐近界。在求解递归式的时候，我们往往会忽略一些技术细节，例如归并排序中，如果$n$是奇数，那么分解的子问题规模不是准确的$n/2$，而是其向下向上取整后的结果。一般来说这种细节不会对最终的渐近界有什么影响。

最大子数组

最大子数组问题描述的是对于一个数组，我们想要找到和最大的连续子数组。最简单的方法就是暴力解法了。因为边界端点的组合最多也就只有$C_n^2$种，计算每种组合的子数组和的代价至少是常量，因此这样的情况下时间复杂度是$\Omega(n^2)$。