数据结构中的代入法

在这里，我们将了解如何使用代入法来解决递推关系。我们将通过两个例子来更好地理解它。

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

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

求解 - 我们将在每一步中代入公式以获得结果 -

$$T(n)=T(\frac{n}{2})+c$$

通过代入 T(N/2) 我们可以写成，

$$T(n)=(T(\frac{n}{4})+c)+c$$

$$T(n)=T(\frac{n}{4})+2c$$

$$T(n)=T(\frac{n}{8})+3c$$

$$T(n)=T(\frac{n}{2^{k}})+kc$$

现在如果 $$(\frac{n}{2^{k}})$$ 达到 1，则表示 2^k 等于 n。所以 k 的值为 log₂𝑛

T(n) 的复杂度为 ϴ(log n)

类似地，如果我们选择另一个例子，比如归并排序，那么在这种情况下，我们将列表分成两部分。这种划分会持续进行，直到列表大小仅为 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}$$

求解 - 我们将在每一步中代入公式以获得结果 -

$$T(n)=2T(\frac{n}{2})+cn$$

通过代入 T(N/2) 我们可以写成，

$$T(n)=2(2T(\frac{n}{4})+\frac{cn}{2}) +cn$$

$$T(n)=4T(\frac{n}{4}) +2cn$$

$$T(n)=8T(\frac{n}{8}) +3cn$$

$$T(n)=2^{k}T(\frac{n}{2^{k}}) +kcn$$

现在如果 $$(\frac{n}{2^{k}})$$ 达到 1，则表示 2^k 等于 n。所以 k 的值为 log₂𝑛。而 T(n) 将为 -

𝑇(𝑛) = 𝑛𝑇(1) + 𝑐𝑛 log₂𝑛

复杂度为 θ(n log n)

Arnab Chakraborty

更新于: 2020年8月10日

5K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习