NOTE: 演算法的量級

給定複雜度函數 f(n)，O(f(n)) 為複雜度函數 g(n) 構成之集合。其中，對任意 g(n)，必存在正實數 c 與非負整數 N，使所有 n ≥ N，g(n) ≤ c × f(n)

這看似很難理解的定義其實在說一件很簡單的事：g(n) 會在某個點 N 落在 c × f(n) 下方

拿一些常見的 f(n) 來觀察用途非常不錯，令 f(n) 為 n²，g(n) 為 n²+20n。用 n²+20n ≤ n²+20n² = 21n² 就可以得到 c=21、N=1 證明 n²+20n ∈ O(n²)。 很重要的關鍵就是不是只有一組條件會符合，例如說我們也可以用 n²+20n ≤ 2n² 這個不等式導出 20n ≤ n² 取 c=2、N=20 證明 n²+20n ∈ O(n²)。 所以前面才會特別提到量級的條件寬鬆。另外就是由於太多人喜歡背誦 n² log n 之類的函數，而忽略了複雜度函數並不只有這些的事實， 我們可以設計一個簡單的案例來破除這個迷思，n² ∈ O(n² + n) 可以取 c=1、N=0 得證。

這個案例同時也說明了 g(n) ∈ O(f(n)) ∧ f(n) ∈ O(g(n)) 完全是可能的(稍微試著證明 n²+n ∈ O(n²) 吧)

要記住 O 很寬鬆，例如說我們也可以令 f(n) = n²，g(n) = n。 對 c=1、N=0，n ≤ n² 成立，於是得證 n 落在 O(n²) 中，但這個資訊沒什麼鳥用，我們沒辦法用過度寬鬆的上限改善演算法。 所以才需要 Ω 這個概念

Ω 函數的定義正巧與 O 相反，是用來定義下限的：

給定複雜度函數 f(n)，Ω(f(n)) 為複雜度函數 g(n) 構成之集合。其中，對任意 g(n)，必存在正實數 c 與非負整數 N，使所有 n ≥ N，g(n) ≥ c × f(n)

並不偶然的是 Ω 同樣寬鬆與沒什麼用處，真正有用的是兩者的交集：Θ

而通常很多人講 big O 其實都是在說 Θ，g ∈ Θ(n²) 表示我們可以藉由某個純平方函數的倍數來描述 g 的最終上下界(實務上應該關心一下這時候 N 到底是多少會比較好 XD)， 作為效能的依據。

其實我已經講了但還是寫一下：Θ(f(n)) = O(f(n)) ∩ Ω(f(n))