資料結構 - 漸近分析

---

---

漸近分析

演算法的漸近分析是指定義其執行時間效能的數學基礎/框架。使用漸近分析，我們可以很好地得出演算法的最佳情況、平均情況和最壞情況。

漸近分析是輸入相關的，即如果演算法沒有輸入，則認為其在常數時間內完成。除“輸入”外，所有其他因素都被認為是常數。

漸近分析是指用數學計算單位計算任何操作的執行時間。例如，一個操作的執行時間計算為f(n)，而另一個操作的執行時間計算為g(n²)。這意味著第一個操作的執行時間將隨著n的增加而線性增加，而第二個操作的執行時間將隨著n的增加而呈指數增加。類似地，如果n非常小，則兩個操作的執行時間將大致相同。

通常，演算法所需的時間分為三種類型：

• 最佳情況 - 程式執行所需的最小時間。

• 平均情況 - 程式執行所需的平均時間。

• 最壞情況 - 程式執行所需的最多時間。

漸近記號

演算法的執行時間取決於指令集、處理器速度、磁碟I/O速度等。因此，我們漸近地估計算法的效率。

演算法的時間函式用T(n)表示，其中n是輸入大小。

不同型別的漸近記號用於表示演算法的複雜性。以下漸近記號用於計算演算法的執行時間複雜性。

• O - 大O記號

• Ω - 大Ω記號

• θ - 大θ記號

• o - 小o記號

• ω - 小ω記號

大O，O：漸近上界

記號Ο(n)是表示演算法執行時間上界的正式方法。是最常用的記號。它衡量最壞情況時間複雜度或演算法可能完成所需的最長時間。

如果存在正整數n的值為n₀和正常數c，則函式f(n)可以表示為g(n)的階，即O(g(n))，使得：

$f(n)\leqslant c.g(n)$ 對於所有情況下的$n > n_{0}$

因此，函式g(n)是函式f(n)的上界，因為g(n)的增長速度快於f(n)。

示例

讓我們考慮一個給定的函式，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

考慮$g(n) = n^3$，

$f(n)\leqslant 5.g(n)$ 對於所有$n > 2$的值

因此，f(n)的複雜度可以表示為$O(g(n))$，即$O(n^3)$

大Ω，Ω：漸近下界

記號Ω(n)是表示演算法執行時間下界的正式方法。它衡量最佳情況時間複雜度或演算法可能完成所需的最短時間。

當存在常數c使得$f(n)\geqslant c.g(n)$對於所有足夠大的n值成立時，我們說$f(n) = \Omega (g(n))$。這裡n是正整數。這意味著函式g是函式f的下界；在某個n值之後，f永遠不會低於g。

示例

讓我們考慮一個給定的函式，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$。

考慮$g(n) = n^3$，$f(n)\geqslant 4.g(n)$對於所有$n > 0$的值。

因此，f(n)的複雜度可以表示為$\Omega (g(n))$，即$\Omega (n^3)$

θ，θ：漸近緊界

記號θ(n)是表示演算法執行時間上下界的正式方法。有些人可能會將θ記號誤認為是平均情況時間複雜度；雖然大θ記號可以幾乎準確地用於描述平均情況，但也可以使用其他記號。

當存在常數c₁和c₂使得$c_{1}.g(n) \leqslant f(n) \leqslant c_{2}.g(n)$對於所有足夠大的n值成立時，我們說$f(n) = \theta(g(n))$。這裡n是正整數。

這意味著函式g是函式f的緊界。

示例

讓我們考慮一個給定的函式，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

考慮$g(n) = n^3$，$4.g(n) \leqslant f(n) \leqslant 5.g(n)$對於所有較大的n值。

因此，f(n)的複雜度可以表示為$\theta (g(n))$，即$\theta (n^3)$。

小o，o

O-記號提供的漸近上界可能是也可能不是漸近緊密的。界限$2.n^2 = O(n^2)$是漸近緊密的，但界限$2.n = O(n^2)$不是。

我們使用o-記號來表示不是漸近緊密的界限。

我們正式定義o(g(n))（g(n)的小o）為集合f(n) = o(g(n))，對於任何正常數$c > 0$，都存在一個值$n_{0} > 0$，使得$0 \leqslant f(n) \leqslant c.g(n)$。

直觀地說，在o-記號中，當n趨於無窮大時，函式f(n)相對於g(n)變得微不足道；也就是說，

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = 0$$

示例

讓我們考慮相同的函式，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

考慮$g(n) = n^{4}$，

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^4}\right) = 0$$

因此，f(n)的複雜度可以表示為$o(g(n))$，即$o(n^4)$。

小ω，ω

我們使用ω-記號來表示不是漸近緊密的界限。然而，我們正式定義ω(g(n))（g(n)的小ω）為集合f(n) = ω(g(n))，對於任何正常數C > 0，都存在一個值$n_{0} > 0$，使得$0 \leqslant c.g(n) < f(n)$。

例如，$\frac{n^2}{2} = \omega (n)$，但$\frac{n^2}{2} \neq \omega (n^2)$。關係$f(n) = \omega (g(n))$暗示存在以下極限

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = \infty$$

也就是說，當n趨於無窮大時，f(n)相對於g(n)變得任意大。

示例

讓我們考慮相同的函式，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

考慮$g(n) = n^2$，

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^2}\right) = \infty$$

因此，f(n)的複雜度可以表示為$o(g(n))$，即$\omega (n^2)$。

常用漸近記號

以下是一些常用漸近記號的列表：

常數	-	O(1)
對數	-	O(log n)
線性	-	O(n)
n log n	-	O(n log n)
平方	-	O(n2)
三次方	-	O(n3)
多項式	-	nO(1)
指數級	-	2O(n)

先驗和後驗分析

先驗分析是指在演算法運行於特定系統之前進行的分析。這種分析階段使用某種理論模型定義函式。因此，我們只需檢視演算法本身，無需在具有不同記憶體、處理器和編譯器的特定系統上執行它，即可確定演算法的時間和空間複雜度。

演算法的後驗分析是指僅在系統執行演算法之後才進行的分析。它直接依賴於系統，並且會因系統而異。

在行業中，我們無法進行後驗分析，因為軟體通常是為匿名使用者開發的，這些使用者會在與行業中存在的系統不同的系統上執行它。

在先驗分析中，我們使用漸近符號來確定時間和空間複雜度的原因是，它們會因計算機而異；但是，漸近地它們是相同的。