0401概述-分治策略-算法导论第三版

本文主要是介绍0401概述-分治策略-算法导论第三版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- - 1 概述
  - 2 递归式
  - 3 递归式技术细节
- 结语

1 概述

在分治策略中，我们递归地求解一个问题，在每层递归中应用如下三个步骤：

分解：将问题划分为一些规模更小形式一样的子问题。
解决：递归求解子问题。如果子问题规模足够小，停止递归，直接求解。
合并：将子问题的解组合成原问题的解。

当子问题规模足够大，需要递归求解时，我们称之为 递归情况。当子问题变得足够小，不需要递归时，进入 基本情况。有时，除了与原问题形式完全一样的规模更小的子问题外，还需要求解与原问题形式不完全一样的子问题。我们将这些子问题的求解看做合并步骤的一部分。

2 递归式

递归式与分治方法是紧密相关的，因为使用递归式可以很自然地刻画分治算法的运行时间。一个递归式就是一个不等式或等式，它通过更小的输入上的函数值来描述一个函数。

递归式有很多形式。

子问题的规模不必是原问题规模的一个固定比例。

求解递归式的方法，可得出算法 $\Theta 或\Omicron$ 渐进界

代入法：我们猜测一个界，然后用数学归纳法证明这个界是正确的。
递归树法：将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。
主方法：可求解形如下面公司的递归式的界。 $T (n) = a T (n / b) + f (n)$ ,其中 $a\ge 1,b\gt 1,f(n)$ 是一个给定的函数。这种形式的递归式很常见，它刻画了一个分治算法：生成a个子问题，每个子问题的规模是原问题规模的 $\frac{1}{b}$ ，分解和合并步骤总共花费时间为 $f (n)$

我们遇到不是等式而是不等式的递归式，例如 $T(n)\le 2T(n/2)+\Theta(n)$ ,该递归式描述了 $T (n)$ 的一个上界，可以用 $\Omicron$ 来描述其解。同样的，如果是不等式 $T(n)\ge 2T(n/2)+\Theta(n)$ ，可以用 $\Omega$ 来描述其解。