資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究資料結構中的代入法
在這裡，我們將瞭解如何使用代入法來解決遞推關係。我們將透過兩個例子來更好地理解它。
假設我們正在使用二分查詢技術。在這種技術中，我們檢查元素是否存在於末尾。如果它存在於中間，則演算法終止，否則我們一次又一次地從實際陣列中取左子陣列和右子陣列。因此，在每一步中，陣列的大小都會減小 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，則表示 2k 等於 n。所以 k 的值為 log2𝑛
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，則表示 2k 等於 n。所以 k 的值為 log2𝑛。而 T(n) 將為 -
𝑇(𝑛) = 𝑛𝑇(1) + 𝑐𝑛 log2𝑛
複雜度為 θ(n log n)
5K+ 瀏覽量
