演算法/數學背景

頂部，章節：1，2，3，4，5，6，7，8，9，A

在我們開始學習演算法技術之前，我們將先繞道介紹一些必要的數學工具。首先，我們將介紹一些將在本書後面使用的術語的數學定義。透過擴充套件你的數學詞彙，你可以更加精確地描述問題或更容易地表達問題。然後，我們將介紹分析演算法執行時間的方法。在本專著中，我們將在介紹每個主要演算法之後給出其執行時間的分析以及其正確性的證明。

漸進符號

除了正確性之外，另一個重要的演算法特徵是其時間和記憶體消耗。時間和記憶體都是寶貴的資源，它們在使用方式上存在顯著差異（即使兩者都充足）。

如何衡量資源消耗？一種方法是建立一個函式，用輸入的一些特徵來描述資源的使用情況。一個常用的輸入資料集特徵是其大小。例如，假設一個演算法以一個包含 $n$ 個整數的陣列作為輸入。我們可以將這個演算法所需的時間描述為一個以 $n$ 為變數的函式 $f$。例如，我們可以寫成

$f(n)=n^{2}+3n+14$

其中 $f(n)$ 是某個時間單位（在本討論中，主要關注的是時間，但我們也可以用它來描述記憶體消耗）。時間單位很少是實際的秒數，因為這會取決於機器本身、它執行的系統以及系統負載。相反，時間單位通常用執行某些基本操作的次數來表示。例如，我們可能關心的一些基本操作包括：所需的加法或乘法次數；元素比較次數；記憶體位置交換次數；或執行的機器指令數量。通常，我們可能會簡單地將這些執行的基本操作稱為執行的步驟。

這是否是確定演算法資源消耗的好方法？是也不是。當兩種不同的演算法在時間消耗上相似時，精確的函式可能有助於確定在給定條件下哪個演算法更快。但在許多情況下，計算執行所需操作確切數量的解析描述要麼很困難，要麼根本不可能，尤其是在演算法根據其輸入的值有條件地執行操作時。相反，真正重要的是不是完成函式所需的精確時間，而是資源消耗根據其輸入變化的程度。具體而言，考慮以下兩個函式，它們分別代表每個輸入資料集大小所需的計算時間

$f(n)=n^{3}-12n^{2}+20n+110$

$g(n)=n^{3}+n^{2}+5n+5$

它們看起來很不同，但它們的行為如何？讓我們看看函式的一些影像（$f(n)$ 為紅色，$g(n)$ 為藍色）

f 和 g 在 0 到 5 範圍內的影像	f 和 g 在 0 到 15 範圍內的影像
f 和 g 在 0 到 100 範圍內的影像	f 和 g 在 0 到 1000 範圍內的影像

在第一個非常有限的影像中，曲線看起來有些不同。在第二個影像中，它們開始以某種方式呈現相同的趨勢，在第三個影像中，它們之間只有很小的差異，最後它們幾乎完全相同。實際上，它們逼近 $n^{3}$，即主導項。當 n 變大時，其他項與 n³ 相比變得微不足道。

正如你所看到的，修改多項式時間演算法的低階係數並沒有太大幫助。真正重要的是最高階係數。這就是為什麼我們採用了這種符號來進行這種分析。我們說

$f(n)=n^{3}-12n^{2}+20n+110=O(n^{3})$

我們忽略了低階項。我們可以說

$O(\log {n})\leq O({\sqrt {n}})\leq O(n)\leq O(n\log {n})\leq O(n^{2})\leq O(n^{3})\leq O(2^{n})$

這為我們提供了一種更便捷的方式來比較不同的演算法。對$n$個元素進行插入排序需要$O(n^{2})$數量級的步驟。歸併排序的排序步驟為$O(n\log {n})$。因此，一旦輸入資料集足夠大，歸併排序就會比插入排序更快。

一般來說，我們寫

$f(n)=O(g(n))$

當

$\exists c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq f(n)\leq c\cdot g(n).$

也就是說，$f(n)=O(g(n))$成立當且僅當存在一些常數$c$和$n_{0}$，使得對於所有$n>n_{0}$，$f(n)$為正且小於等於$cg(n)$。

注意，此符號中使用的等號描述了$f(n)$和$g(n)$之間的關係，而不是反映真正的相等性。鑑於此，有些人用集合來定義大O符號，指出

$f(n)\in O(g(n))$

當

$f(n)\in \{f(n):\exists c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq f(n)\leq c\cdot g(n)\}.$

大O符號只是一個上界；這兩個都是真的

$n^{3}=O(n^{4})$

$n^{4}=O(n^{4})$

如果我們將等號用作等式，我們會得到非常奇怪的結果，例如

$n^{3}=n^{4}$

這顯然是胡說八道。這就是為什麼集合定義很方便。你可以透過將等號視為單向等式來避免這些情況，即

$n^{3}=O(n^{4})$

並不意味著

$O(n^{4})=n^{3}$

始終將 O 保持在右側。

大 Omega

有時，我們想要更多地瞭解某個函式行為的上界。大 Omega 提供了下界。一般來說，我們說

$f(n)=\Omega (g(n))$

當

$\exists c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq c\cdot g(n)\leq f(n).$

即 $f(n)=\Omega (g(n))$ 當且僅當存在常數 c 和 n₀ 使得對於所有 n>n₀ f(n) 為正且大於或等於 cg(n)。

所以，例如，我們可以說

$n^{2}-2n=\Omega (n^{2})$，(c=1/2, n₀=4) 或

$n^{2}-2n=\Omega (n)$，(c=1, n₀=3)，

但聲稱

$n^{2}-2n=\Omega (n^{3}).$

大 Theta

當給定函式同時為 O(g(n)) 和 Ω(g(n)) 時，我們說它是 Θ(g(n))，並且我們對該函式有了嚴格的界限。函式 f(n) 為 Θ(g(n)) 時

$\exists c_{1}>0,\exists c_{2}>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq c_{1}\cdot g(n)\leq f(n)\leq c_{2}\cdot g(n),$

但大多數時候，當我們試圖證明給定的 $f(n)=\Theta (g(n))$ 時，我們並不使用這個定義，而是證明它同時是 O(g(n)) 和 Ω(g(n))。

小 O 和 Omega

當漸近界限不緊密時，我們可以用 $f(n)=o(g(n))$ 或 $f(n)=\omega (g(n)).$ 來表達。定義如下：

f(n) 是 o(g(n)) 當且僅當 $\forall c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq f(n)<c\cdot g(n)$，並且

f(n) 是 ω(g(n)) 當且僅當 $\forall c>0,\exists n_{0}>0,\forall n\geq n_{0}:0\leq c\cdot g(n)<f(n).$

請注意，當對於 g 的任何係數，g 最終都大於 f 時，函式 f 屬於 o(g(n))；而對於 O(g(n))，只需要存在一個係數，使得 g 最終至少與 f 一樣大。

大O 多變數

給定兩個引數的函式 $f(n,m)$ 和 $g(n,m)$，

$f(n,m)=O(g(n,m))$ 當且僅當 $\exists c>0,\exists n_{0}>0,\exists m_{0}>0,\forall n\geq n_{0},\forall m\geq m_{0}:0\leq f(n,m)\leq c\cdot g(n,m)$。

例如，$5n+3m=O(n+m)$，以及 $n+10m+3nm=O(nm)$。

演算法分析：求解遞迴方程

合併排序 n 個元素：$T(n)=2*T(n/2)+c(n)$ 這描述了合併排序的一次迭代：問題空間 $n$ 被縮減成兩個一半 ($2*T(n/2)$)，然後在所有遞迴呼叫結束時合併在一起 ($c(n)$)。這個符號系統是演算法分析的精髓，所以要習慣它。

有一些定理可以用來估計一個函式的 Big Oh 時間，前提是它的遞迴方程符合某種模式。

替換法

對你的方程的 Big Oh 時間做一個猜測。然後使用歸納法證明這個猜測是正確的。

畫樹和表

這實際上只是一種獲得明智猜測的方法。你仍然必須回到替換法來證明 Big Oh 時間。

主定理

考慮一個遞迴方程，它符合以下公式

$T(n)=aT\left({\frac {n}{b}}\right)+O(n^{k})$

對於 a ≥ 1, b > 1 和 k ≥ 0。這裡，a 是每次函式呼叫產生的遞迴呼叫次數，n 是輸入大小，b 是每次輸入縮小多少，k 是每次函式呼叫（除了基本情況）執行的操作的多項式階數。例如，在後面介紹的合併排序演算法中，我們有

$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$

因為每次非基本情況迭代都會呼叫兩個子問題，並且陣列的大小每次都會減半。最後的 $O(n)$ 是這個分治演算法的“征服”部分：將兩個遞迴呼叫的結果合併成最終結果需要線性時間。

將 T 的遞迴呼叫視為形成一棵樹，有三種可能的情況來確定演算法的大部分時間都花在哪裡（這裡“大部分”指的是它的漸進行為）

1. 這棵樹可能是頭重腳輕的，大部分時間花在接近根部的初始呼叫上；
2. 這棵樹可能有一個穩定狀態，時間均勻分佈；或者
3. 這棵樹可能頭輕腳重，大部分時間花在接近葉子的呼叫上

根據樹處於這三種狀態中的哪一種，T 將有不同的複雜度

主定理

假設給定 $T(n)=aT\left({\frac {n}{b}}\right)+O(n^{k})$ 對於 a ≥ 1, b > 1 和 k ≥ 0

• 如果 $a<b^{k}$，那麼 $T(n)=O(n^{k})\$ （頭重腳輕）
• 如果 $a=b^{k}$，則 $T(n)=O(n^{k}\cdot \log n)$（穩定狀態）
• 如果 $a>b^{k}$，則 $T(n)=O(n^{\log _{b}a})$（底部沉重）

對於上面提到的歸併排序示例，其中

$T(n)=2T\left({\frac {n}{2}}\right)+O(n)$

我們有

$a=2,b=2,k=1\implies b^{k}=2$

因此，$a=b^{k}$，所以這也處於“穩定狀態”：根據主定理，歸併排序的複雜度因此為

$T(n)=O(n^{1}\log n)=O(n\log n)$.

均攤分析

（從圖的鄰接表表示開始，並顯示兩個巢狀的for迴圈：一個用於每個節點n，另一個巢狀在該迴圈中，用於每個邊e。如果有n個節點和m個邊，這可能導致你說迴圈需要O(nm)時間。但是，只有在一次迴圈中，內部迴圈才能花費那麼長時間，更緊密的界限是O(n+m)。）

---

頂部，章節：1，2，3，4，5，6，7，8，9，A