分析方法

---

---

為了衡量演算法的資源消耗，使用了不同的策略，如本章所述。

漸近分析

函式f(n)的漸近行為是指n變大時f(n)的增長情況。

我們通常忽略n的小值，因為我們通常感興趣的是估計程式在大型輸入上的執行速度。

一個好的經驗法則是，漸近增長率越慢，演算法越好。儘管這並不總是正確的。

例如，線性演算法$f(n) = d * n + k$在漸近意義上總是優於二次演算法$f(n) = c.n^2 + q。

求解遞推方程

遞推關係是一個用較小輸入上的函式值來描述函式的方程或不等式。遞推關係通常用於分治正規化。

讓我們考慮T(n)為大小為n的問題的執行時間。

如果問題規模足夠小，例如n < c，其中c是一個常數，則直接解法需要常數時間，寫成θ(1)。如果問題的劃分產生了一些大小為$\frac{n}{b}$的子問題。

為了解決這個問題，所需時間為a.T(n/b)。如果我們考慮劃分所需的時間為D(n)，組合子問題結果所需的時間為C(n)，則遞推關係可以表示為 -

$$T(n)=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\theta(1) & if\:n\leqslant c\\a T(\frac{n}{b})+D(n)+C(n) & otherwise\end{cases}$$

可以使用以下方法求解遞推關係 -

• 代入法 - 在這種方法中，我們猜測一個界限，並使用數學歸納法證明我們的假設是正確的。

• 遞迴樹法 - 在這種方法中，形成一個遞迴樹，其中每個節點代表成本。

• 主定理 - 這是另一種找到遞推關係複雜度的重要技術。

攤還分析

攤還分析通常用於執行一系列類似操作的某些演算法。

• 攤還分析提供整個序列的實際成本的上界，而不是分別對操作序列的成本進行邊界限制。

• 攤還分析不同於平均情況分析；機率不涉及攤還分析。攤還分析保證了最壞情況下每個操作的平均效能。

它不僅僅是一個分析工具，它是一種思考設計的思路，因為設計和分析是密切相關的。

聚合方法

聚合方法提供了問題的全域性檢視。在這種方法中，如果n個操作總共需要最壞情況時間T(n)。那麼每個操作的攤還成本為T(n)/n。雖然不同的操作可能需要不同的時間，但在這種方法中忽略了變化的成本。

記賬方法

在這種方法中，根據操作的實際成本為不同的操作分配不同的費用。如果操作的攤還成本超過其實際成本，則將差額作為信用分配給物件。此信用有助於支付攤還成本低於實際成本的後續操作。

如果第i^th個操作的實際成本和攤還成本為$c_{i}$和$\hat{c_{l}}$，則

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}\geqslant\displaystyle\sum\limits_{i=1}^n c_{i}$$

勢能方法

此方法將預付工作表示為勢能，而不是將預付工作視為信用。這種能量可以釋放出來支付未來的操作。

如果我們執行n個操作，從初始資料結構D₀開始。讓我們考慮c_i為實際成本，D_i為第i^th個操作的資料結構。勢函式Ф對映到一個實數Ф(D_i)，即D_i的相關勢能。攤還成本$\hat{c_{l}}$可以定義為

$$\hat{c_{l}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})$$

因此，總的攤還成本為

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}=\displaystyle\sum\limits_{i=1}^n (c_{i}+\Phi (D_{i})-\Phi (D_{i-1}))=\displaystyle\sum\limits_{i=1}^n c_{i}+\Phi (D_{n})-\Phi (D_{0})$$

動態表

如果為表分配的空間不足，則必須將表複製到更大的表中。類似地，如果從表中刪除了大量成員，則最好將表重新分配為更小的尺寸。

使用攤還分析，我們可以證明插入和刪除的攤還成本是常數，並且動態表中未使用的空間永遠不會超過總空間的常數部分。

在本教程的下一章中，我們將簡要討論漸近符號。