閱讀前，建議可以參考Day1：閱讀指南＆為何選擇這個題目？

▌挑戰簡介

• 題目：計算機概論Ｘ30天

• 挑戰內容：連續30天紀錄計算機概論、離散數學、演算法、資料結構等課程，還有自己學習程式的心得體悟。

• 本篇性質：沒有必要閱讀，因為寫得沒有很仔細，而且我覺得不知道公式的證明法也沒關係。

▌前言

在Day5：[演算法]如何衡量程式的效率？——論時間複雜度（Time Complexity）討論了如何計算複雜度，比如說

消耗了2t(時間單位) => 時間複雜度是O(1)
消耗了12t(時間單位) => 時間複雜度是O(1)
消耗了(n+2)t(時間單位) => 時間複雜度是O(n)
消耗了(n^2+2)t(時間單位) => 時間複雜度是O(n^2)

但是當時沒有認真證明，因此這篇來套公式證明看看

▌ Big-O notation

以下才是Big-O notation 的數學定義

f(n) = Ο(g(n)) 
iff ∃正常數c和n0，使得f(n) ≤ c × g(n), ∀ n >= n0

若 n^2+2 = O(n^2)
則必須找得到K和C，使得 n^2+2<=Cn^2 (∀n>n0)
比如說當C=100 n0=1
那n^2+2<=Cn^2 (∀n>n0)恆成立
因此可以知道 n^2+2 = O(n^2)

簡單來說，這個公式的意思就是，不管怎樣，g(n)的成長速率一定快於或等於f(n)