数据结构中的递推方程

在算法分析中，我们发现一些递推关系。这些递推关系基本上是在表达式中使用相同的函数。在大多数情况下，对于递归算法分析和分治算法，我们都会得到递推关系。

这里我们将通过一些例子来看一个递推方程的例子。假设我们使用二分查找技术。在这种技术中，我们检查元素是否存在于末尾。如果它存在于中间，则算法终止，否则我们一次又一次地从实际数组中取左子数组和右子数组。因此，在每一步中，数组的大小都会减少 n / 2。假设二分查找算法需要 T(n) 的时间来执行。基本条件需要 O(1) 的时间。因此，递推方程如下：

$$T(n)=\begin{cases}T(1) & for\:n \leq 1\T(|\frac{n}{2}\rvert)+c & for\:n > 1\end{cases}$$

类似地，如果我们选择另一个例子，如归并排序，在这种情况下，我们将列表分成两部分。这种划分会一直进行，直到列表大小只有 1。之后，我们将它们按排序顺序合并。合并算法需要 O(n) 的时间。因此，如果归并排序算法需要 T(n) 的时间，那么将其分成两半，并对每一半执行相同的任务，它们将分别需要 T(n/2)，依此类推。因此，递推关系如下：

$$T(n)=\begin{cases}T(1) & for\:n = 1\2T(\frac{n}{2})+cn & for\:n > 1\end{cases}$$

我们可以使用不同的方法来求解这些方程，例如代入法、递推树法，以及一些特殊的递推关系可以使用主方法求解。

Arnab Chakraborty

更新于：2020年8月10日

浏览量 1K+

启动您的职业生涯

完成课程获得认证

开始学习