iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 26
0
自我挑戰組

計算機概論X30天系列 第 26

Day26:[離散數學]複雜度的數學證明

閱讀前,建議可以參考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

以下才是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)


上一篇
Day 24:[計算機概論]如果把加減乘除串起來用?——Toy Machine的ALU結構
下一篇
Day27:阿姆達爾定律(Amdahl's law)——資源配置的哲學
系列文
計算機概論X30天30

尚未有邦友留言

立即登入留言