資料結構中的遞推方程

在演算法分析中，我們發現一些遞推關係。這些遞推關係基本上是在表示式中使用相同的函式。在大多數情況下，對於遞迴演算法分析和分治演算法，我們都會得到遞推關係。

這裡我們將透過一些例子來看一個遞推方程的例子。假設我們使用二分查詢技術。在這種技術中，我們檢查元素是否存在於末尾。如果它存在於中間，則演算法終止，否則我們一次又一次地從實際陣列中取左子陣列和右子陣列。因此，在每一步中，陣列的大小都會減少 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+

啟動您的職業生涯

完成課程獲得認證

開始學習