閱讀前,建議可以參考Day1:閱讀指南&為何選擇這個題目?
題目:計算機概論X30天
挑戰內容:連續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 的數學定義
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)