資料結構/漸進符號

資料結構
介紹 - 漸進符號 - 陣列 - 列表結構 & 迭代器
棧 & 佇列 - 樹 - 最小堆 & 最大堆 - 圖
雜湊表 - 集合 - 權衡

漸進符號

介紹

不存在一種資料結構可以在所有情況下都提供最佳效能。為了選擇最適合特定任務的資料結構，我們需要能夠判斷特定解決方案需要多長時間才能執行。或者更準確地說，你需要能夠判斷兩種解決方案需要多長時間才能執行，然後選擇其中較好的一個。我們不需要知道它們需要多少分鐘和秒，但我們需要一種方法將演算法相互比較。

漸進複雜度是一種使用理想化的（不可比較的）計算工作單位來表達演算法成本主要部分的方法。例如，考慮對一副撲克牌進行排序的演算法，該演算法透過反覆搜尋牌堆中最低的牌來進行。該演算法的漸進複雜度是牌堆中卡片數量的平方。這種二次行為是複雜度公式中的主要項，它表示，例如，如果你將牌堆的大小加倍，那麼工作量大約會增加四倍。

成本的確切公式更復雜，並且包含比我們理解演算法基本複雜度所需更多的細節。在我們的撲克牌中，在最壞的情況下，牌堆將從反向排序開始，因此我們的掃描必須一直進行到最後。第一次掃描將涉及掃描$52$張牌，下一次掃描將花費$51$張牌，依此類推。因此成本公式是$52+51+\dots +2$。一般來說，讓$N$代表卡片數量，公式是$2+\dots +N$，它等於$N\times {\frac {N+1}{2}}-1={\frac {N^{2}+N}{2}}-1={\frac {1}{2}}\times N^{2}+{\frac {1}{2}}\times N-1$。但$N^{2}$項在表示式中占主導地位，而這對於比較演算法成本至關重要。（這實際上是一個昂貴的演算法；最好的排序演算法在亞二次時間內執行。）

漸進地講，當$N$趨向於無窮大時，$2+3+\dots +N$越來越接近純二次函式${\frac {1}{2}}\times N^{2}$。在如此抽象的層面上，${\frac {1}{2}}$的常數因子有何不同？因此，該行為被稱為$O(n^{2})$。

現在讓我們考慮如何比較兩種演算法的複雜度。令 $f(n)$ 是一個演算法在最壞情況下的成本，表示為輸入大小 $n$ 的函式，而 $g(n)$ 是另一個演算法的成本函式。例如，對於排序演算法，$f(10)$ 和 $g(10)$ 將表示演算法對包含 $10$ 個專案的列表所採取的最大步驟數。如果對於所有 $n\geq 0$ 的值，$f(n)$ 小於或等於 $g(n)$，則複雜度函式為 $f$ 的演算法嚴格來說更快。但是，總的來說，我們對計算成本的關注是針對大輸入的情況；所以，比較 $f(n)$ 和 $g(n)$ 在 $n$ 的小值上的意義不如比較 $f(n)$ 和 $g(n)$ 在超過某個閾值的 $n$ 上的意義更大。

請注意，我們一直在討論演算法效能的界限，而不是給出確切的速度。對一組牌進行排序（使用我們簡單的二次演算法）所需的實際步驟數將取決於牌的初始順序。執行每個步驟的實際時間將取決於我們的處理器速度、處理器快取的狀態等等。在具體的細節上非常複雜，而且與演算法的本質無關。

O 符號

定義

O (讀作大O) 是表達演算法執行時間上界的正式方法。它是衡量演算法完成可能需要的最長時間的指標。我們可以假設它代表程式的“最壞情況”。

更正式地說，對於非負函式，$f(n)$ 和 $g(n)$，如果存在一個整數 $n_{0}$ 和一個常數 $c>0$，使得對於所有整數 $n>n_{0}$，$f(n)\leq cg(n)$，那麼 $f(n)$ 是 $(g(n))$ 的大 O。這記作 $f(n)=O(g(n))$。如果繪製圖表，$g(n)$ 充當您正在分析的曲線 $f(n)$ 的上限。

注意，如果 $f$ 只能取有限值（通常情況下應該如此），那麼這個定義意味著存在一個常數 $C$（可能大於 $c$），使得對於所有 $n$ 的值，$f(n)\leq Cg(n)$。$C$ 的一個合適的值是 $c$ 和 $\max _{1\leq n\leq n_{0}}{\frac {f(n)}{g(n)}}$ 的最大值。

理論示例

那麼，讓我們舉一個 Big-O 的例子。假設 $f(n)=2n+8$，並且 $g(n)=n^{2}$。我們能否找到一個常數 $n_{0}$，使得 $2n+8\leq n^{2}$？數字 $4$ 在這裡有效，得出 $16\leq 16$。對於任何大於 $4$ 的數字 $n$，這個方法仍然有效。由於我們試圖將這個方法推廣到 $n$ 的較大值，而較小的值 $\{1,2,3\}$ 不那麼重要，我們可以說 $f(n)$ 通常比 $g(n)$ 快；也就是說，$f(n)$ 受 $g(n)$ 限制，並且始終小於它。

因此可以說 $f(n)$ 在 $O(n^{2})$ 時間內執行："f-of-n 在 Big-O of n-squared 時間內執行"。

為了找到上界 - Big-O 時間 - 假設我們知道 $f(n)$ 等於（準確地）$2n+8$，我們可以採取一些捷徑。例如，我們可以從執行時間中移除所有常數；最終，在 $n$ 的某個值時，它們變得無關緊要。這使得 $f(n)=2n$。同樣，為了方便比較，我們刪除常數乘數；在本例中為 $2$。這使得 $f(n)=n$。也可以說 $f(n)$ 在 $O(n)$ 時間內執行；這使我們能夠對估計值設定更緊密的（更接近的）上界。

實際例子

$O(n)$：將包含 $n$ 個專案的列表列印到螢幕上，每個專案只檢視一次。

$O(\log _{2}{n})$：取一個包含 $n$ 個專案的列表，將其重複地減半，直到只剩下一個專案。

$O(n^{2})$：取一個包含 $n$ 個專案的列表，並將每個專案與其他所有專案進行比較。

大Ω符號

對於非負函式，$f(n)$ 和 $g(n)$，如果存在整數 $n_{0}$ 和常數 $c>0$ 使得對於所有整數 $n>n_{0}$，$f(n)\geq cg(n)$，那麼 $f(n)$ 是 $\Omega (g(n))$。這表示為 $f(n)=\Omega (g(n))$.

這與大O符號的定義幾乎相同，區別在於 $f(n)\geq cg(n)$，這使得 $g(n)$ 成為下界函式，而不是上界函式。它描述了給定資料規模下 **最佳情況**。

Theta 符號

對於非負函式，$f(n)$ 和 $g(n)$，$f(n)$ 是 $g(n)$ 的 theta 當且僅當 $f(n)=O(g(n))$ 且 $f(n)=\Omega (g(n))$。這表示為 $f(n)=\Theta (g(n))$.

這基本上是在說函式 $f(n)$ 被同一個函式 $g(n)$ 從上方和下方同時限制。

Theta 符號用 Q 表示。

小 o 符號

對於非負函式 $f(n)$ 和 $g(n)$，$f(n)$ 是 $g(n)$ 的小 o，當且僅當 $f(n)=O(g(n))$，但 $f(n)\neq \Theta (g(n))$。這記為 $f(n)=o(g(n))$。

這表示 Big O 的一個鬆散的界限版本。 $g(n)$ 從上方進行限制，但它沒有從下方進行限制。

小 Omega 符號

對於非負函式，$f(n)$ 和 $g(n)$，$f(n)$ 是 $g(n)$ 的小 ω 當且僅當 $f(n)=\Omega (g(n))$，但 $f(n)\neq \Theta (g(n))$。這表示為 $f(n)=\omega (g(n))$.

就像小 o 一樣，這是大 Ω 的等價形式。 $g(n)$ 是函式 $f(n)$ 的一個鬆散的下界；它從底部繫結，但不是從頂部繫結。

漸進符號如何與複雜度分析相關聯

時間比較不是演算法中唯一的問題。還有空間問題。通常，在演算法中會注意到時間和空間之間的權衡。漸進符號使您能夠進行這種權衡。如果您將演算法使用的時間和空間量視為隨時間或空間變化的資料的函式（時間和空間通常分別分析），那麼您可以分析在向程式引入更多資料時如何處理時間和空間。

這在資料結構中很重要，因為您希望結構在您增加它處理的資料量時能有效地執行。但請記住，對於大量資料有效的演算法並不總是對於少量資料簡單且有效的。因此，如果您知道您只處理少量資料，並且您擔心速度和程式碼空間，那麼可以為一個對大量資料執行狀況不佳的函式進行權衡。

一些漸進符號的例子

通常，我們將漸進符號用作一種方便的方法來檢查函式在最壞情況下或最佳情況下可能發生的情況。例如，如果您想編寫一個函式，它搜尋一個數字陣列並返回最小的數字

function find-min(array a[1..n])
  let j := $\infty$
  for i := 1 to n:
    j := min(j, a[i])
  repeat
  return j
end

無論陣列的大小如何，每次執行 find-min 時，我們都必須初始化 i 和 j 整型變數並在最後返回 j。因此，我們可以將函式的這些部分視為常量並忽略它們。

那麼，我們如何使用漸進符號來討論 find-min 函式呢？如果我們搜尋一個包含 87 個元素的陣列，那麼 for 迴圈會迭代 87 次，即使我們遇到的第一個元素恰好是最小值。同樣地，對於 $n$ 個元素，for 迴圈會迭代 $n$ 次。因此，我們說該函式在時間 $O(n)$ 內執行。

那麼這個函式呢

function find-min-plus-max(array a[1..n])
  // First, find the smallest element in the array
  let j := $\infty$;
  for i := 1 to n:
    j := min(j, a[i])
  repeat
  let minim := j
  
  // Now, find the biggest element, add it to the smallest and
  j := $-\infty$;
  for i := 1 to n:
    j := max(j, a[i])
  repeat
  let maxim := j
  
  // return the sum of the two
  return minim + maxim;
end

find-min-plus-max 的執行時間是多少？ 有兩個 for 迴圈，每個迴圈都迭代了 $n$ 次，因此執行時間顯然是 $O(2n)$。 因為 $2$ 是一個常數，我們可以將其丟棄並將其執行時間寫為 $O(n)$。 為什麼可以這樣做？ 如果你還記得大 O 符號的定義，那麼你正在測試其界限的函式可以乘以某個常數。 如果 $f(x)=2x$，我們可以看到如果 $g(x)=x$，那麼大 O 條件成立。 因此 $O(2n)=O(n)$。 此規則對於各種漸進符號都是通用的。

資料結構
介紹 - 漸進符號 - 陣列 - 列表結構 & 迭代器
棧 & 佇列 - 樹 - 最小堆 & 最大堆 - 圖
雜湊表 - 集合 - 權衡