Big-O 表示法

定義

Big-O 表示法的核心是數學符號，用於比較函式的收斂速度。讓 n -> f(n) 和 n -> g(n) 成為自然數上定義的函式。然後我們說 f = O(g) 當且僅當當 n 接近無窮大時 f(n)/g(n) 有界。換句話說，f = O(g) 當且僅當存在常數 A 時，對於所有 n，f(n)/g(n) <= A。

實際上，Big-O 表示法的範圍在數學上有點寬泛，但為了簡單起見，我將其縮小到演算法複雜度分析中使用的範圍：在自然界定義的函式，具有非零值的函式，以及 n 增長的情況到無窮遠。

這是什麼意思？

我們來看一下 f(n) = 100n^2 + 10n + 1 和 g(n) = n^2 的情況。很明顯，這兩個函式都傾向於無窮大，因為 n 傾向於無窮大。但有時知道限制是不夠的，我們也想知道功能接近極限的速度。像 Big-O 這樣的概念有助於通過收斂速度來比較和分類函式。

讓我們通過應用定義來找出 f = O(g)。我們有 f(n)/g(n) = 100 + 10/n + 1/n^2。由於當 n 為 1 並且正在減小時 10/n 為 10，並且由於當 n 為 1 並且還在減小時 1/n^2 為 1，所以我們有 f(n)/g(n) <= 100 + 10 + 1 = 111。定義是滿意的，因為我們已經找到了 f(n)/g(n)（111）和 f = O(g) 的界限（我們說 f 是 n^2 的 Big-O）。

這意味著 f 在與 g 大致相同的速度下傾向於無窮大。現在這似乎是一件奇怪的事情，因為我們發現 f 最多比 g 大 111 倍，換句話說，當 g 增長 1 時，f 增長最多為 111.這似乎在增長快 111 倍並不是大致相同的速度。事實上，Big-O 符號並不是一種非常精確的方法來對函式收斂速度進行分類，這就是為什麼在數學中我們在需要精確的速度估計時使用等價關係 。但是為了在大速度類中分離演算法，Big-O 就足夠了。我們不需要將相互之間生成固定次數的函式分開，而只需要無限增長的函式 ** 比彼此快。舉例來說，如果我們採取 h(n) = n^2*log(n)，我們看到 h(n)/g(n) = log(n) 趨向於無窮大與正因此 h 是不為 O（n ^ 2），因為^ h 成長無限小於 n ^ 2 更快。

現在我需要做一個旁註：你可能已經注意到，如果 f = O(g) 和 g = O(h)，那麼 f = O(h)。例如在我們的例子中，我們有 f = O(n^3) 和 f = O(n^4) …在演算法複雜度分析中，我們經常說 f = O(g) 意味著 f = O(g) 和 g = O(f)，可以理解為“g 是 f 的最小 Big-O”。在數學中我們說這些函式是彼此的大相互作用。

怎麼用？

在比較演算法效能時，我們對演算法執行的運算元感興趣。這稱為時間複雜度。在這個模型中，我們認為每個基本操作（加法，乘法，比較，賦值等）需要一定的時間，我們計算這些操作的數量。我們通常可以將此數字表示為輸入大小的函式，我們稱之為 n。遺憾的是，這個數字通常會隨著 n 增長到無窮大（如果沒有，我們說演算法是 O(1)）。我們在 Big-O 定義的大速度類中分離我們的演算法：當我們談論“O（n ^ 2）演算法”時，我們的意思是它執行的運算元，表示為 n 的函式，是 O（ N ^ 2）。這表示我們的演算法大致與演算法一樣快，該演算法可以執行大量等於其輸入大小的平方的演算法，或更快。 或更快部分是因為我使用 Big-O 而不是 Big-Theta，但通常人們會說 Big-O 意味著 Big-Theta。

在計算操作時，我們通常會考慮最壞的情況：例如，如果我們有一個最多可以執行 n 次且包含 5 次操作的迴圈，那麼我們計算的運算元就是 5n。也可以考慮平均案例複雜性。

快速說明：快速演算法是執行少量操作的演算法，因此如果運算元量增長到無限快，則演算法速度較慢 ：O(n) 優於 O（n ^ 2）。

我們有時也對演算法的空間複雜性感興趣。為此，我們將演算法佔用的記憶體中的位元組數視為輸入大小的函式，並以相同的方式使用 Big-O。