什麼是 Big-O-notation
Big-O-notation 是我們分析演算法效率的時候，很常使用的一個標記方式。
通常會用來處理演算法的時間複雜度或者空間複雜度。
什麼是時間複雜度
時間複雜度概括來說，就是分析某個演算法運作所需要的時間
不過在資訊領域內，當我們在分析程式運作的時間時，我們發現到一件事情
由於硬體科技的快速發展，我們討論某個演算法所花費的時間時
常常會由於硬體的下一代進步，導致時間需要重新討論
因此，我們在進行演算法分析時，除了分析實際所需的時間
我們更看重 演算法隨輸入大小改變，所導致花費的時間改變。
除了問某筆輸入資料下，這個演算法要花費的時間以外，
我們也會問：如果下一筆輸入資料，是這個資料的 n 倍大
那麼演算法要多花費的時間是？
一樣久？n 倍時間？或者是 2n 倍時間？
後面這個問題，在某些使用場景下，是非常關鍵的問題。
Big-O-notation 的想法
Big-O-notation 的大概思維是
如果我們可以說，下一筆輸入資料，是先前資料的 n 倍大時
我們大概知道演算法要花費的時間
不會超過 g(n) 倍時間
（這邊的 g() 可以是任何函數，像是 x、x2、2x、xx、⋯⋯等等）
那麼我們就可以用 Big-O-notation
f(x) = O(g(x))
來標記該演算法所花費的時間
正式的 Big-O-notation 定義
正式的 Big-O-notation 如下：
假設 x 為輸入資料的大小（幾個 Byte，幾 KB ⋯⋯ 等）
f(x) 為某個演算法在這個輸入下，所花費的時間
設定某個函數為 g(x)
若存在兩個實數 x_0 和 M，
使得對所有的輸入 x > x_0，必定滿足 f(x) <= M × g(x)
我們可以說
f(x) = O(g(x))
舉例
常數時間
假設某個演算法的時間 f(x) ，其數值是某個大於零，固定的常數 C
那麼我們令 g(x) = 1，M = 2 × C，x_0 = 0
對所有的輸入 x > 0，我們可以推論
f(x) = C
=> C <= 2 × C
=> 2 × C = M × 1
因此我們得證，f(x) = O(1)
這個推論適用於任意大的常數 C
這也是為什麼在討論演算法時間複雜度時
通常以 O(1) 表達某個演算法為常數時間
對數時間
假設某個演算法的時間 f(x)
其數值為 log0.1x
那麼，如果我們令 g(x) = log2x
是否能得證 f(x) = O(g(x)) 呢？
這邊我們要利用對數運算
令 x_0 = 0，M = log0.12
我們會發現對所有輸入 x > 0，我們可以推論
f(x) = log2x
=> log0.1x <= log0.12 × log2x
=> log0.12 × log2x = M × g(x)
這個推論適用任何底數的對數函數
所以我們會發現
在討論時間複雜度時
底數的資訊是可以省略的
這也是為什麼在討論演算法時間複雜度時
通常以 O(log n) 表達某個演算法為對數時間
直接省略底數的資訊
線性時間加上常數
假設我們原本有個演算法 F_1，時間複雜度是 O(n)
另一個演算法 F_2 的所消耗的時間
為原本的演算法消耗的時間
加上一個常數時間 C
F_2 的時間是否還包含在 O(n) 裡面呢？
答案是肯定的。
首先，我們根據定義可以知道
F_1 所消耗的時間 f_1(x) = O(n)
所以，必定存在實數 x_0 和 M
使得所有輸入 x > x_0，滿足 f_1(x) <= M × x
我們已知 F_2 所消耗的時間 f_2(x) 為 f_1(x) + C
因此，我們可以令 M_1 = M + C / x_0
若 x > x_0
M_1 × x
= (M + C / x_0 ) × x
= M × x + C × x / x_0
x > x_0，所以 x / x_0 > 1
C × x / x_0 ＞ C
得證 M_1 × x ＞ M × x + C
利用這件事情，我們可以推論
對所有輸入 x > x_0
f_2(x) = f_1(x) + C
f_1(x) + C <= M × x + C
M × x + C < M_1 × x
所以 f_2(x) <= M_1 × x
f_2(x) = O(n)
除了 O(n) 之外
這件事情在非常多的函數上均成立
所以一般來說，我們在計算時間複雜度時
會傾向忽略常數部分的時間