標題:
[【學科】]
【問題】Big-O
[打印本頁]
作者:
43777061
時間:
2018-7-11 20:52
標題:
【問題】Big-O
本帖最後由 43777061 於 2018-7-11 22:19 編輯
10n^2+5n+1=O(n^3)
為甚麼? 書上的解釋是:
「原來10n^2+5n+1∈O(n^2)，而n^3又大於n^2，理所當然10n^2+5n+1=O(n^3)是沒問題的。」
Big-O不是用來表達成長方式的嗎? 10n^2+5n+1這個多項式一看就知道它是指數成長，為什麼它的Big-O是O(n^3)?
更新（自問自答）：
我去查了Big-O的定義（書上的定義看得不是很懂），已經了解了
令f(n)=10n^2+5n+1
因為找得到c*n^3≥f(n)，∀n≥n0
所以f(n)∈O(n^3)
作者:
39475494
時間:
2018-7-24 00:57
它不是指數成長，它是平方成長。
e^n 才是指數成長。
這題f(n)∈O(n^2)吧？
找的到 c*n^2≥f(n)，∀n≥n0
其中 c=11，n0=6
作者:
33144653
時間:
2018-7-24 11:32
這是計概的時間複雜度?
作者:
39475494
時間:
2018-7-24 12:13
這是計概的時間複雜度?
33144653 發表於 2018-7-24 11:32
是這是函數成長的情況
也可以拿來看程式演算時花的時間程度(複雜度)。
歡迎光臨 Discuz! Board (http://bbs.61.com.tw/)
Powered by Discuz! 7.2
