推 kusoayan :厲害XD 11/11 11:35
※ 引述《gogosk8 (小郭)》之銘言：
: ※ 引述《chiron127 (黑潮)》之銘言：
: : 我的數學底子很不好，所以不確定這算「代數」問題還是「其他」
: : 手邊有一題Big-O的問題，Google加維基後還是有些地方不清楚
: : 希望版上高手能釋疑，謝謝
: : Big-O notation 定義：
: : 若且唯若 f(n)＝O(g(n))
: : 則存在有正數常數 c 與 n0，使得 n ＞＝ n0 時，
: : ∣f(n)∣＜＝ c ﹡∣g(n)∣
: : 題目：請證明
: : f(n)＝2n^2＋9n＋10
: : g(n)＝n^2
: : f(n)＝O(g(n))
: : 推導：
: 我的解法：
: 對任意正整數n ,
: f(n) 2n^2＋9n＋10 9 10
: ---- = -------------- = 2 + --- + ----
: g(n) n^2 n n^2 .
: f(n)
: ---- ------> 2 as n ----> ∞
: g(n)
: 因此,存在一個正整數N 使得
: f(n)
: if n>N ,then [ ---- - 2 ]< 1 []代表絕對值
: g(n)
: 所以絕對值拆開就符合big O 的定義了
直接用估的可能會快一些...
for n>=10
|f(n)|<=2|n^2|+10|n|+100
<=2|n^2|+|n^2|+|n^2|
=4|n^2|
=4|g(n)|
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.49.190
※ 編輯: qllvv 來自: 140.113.49.190 (11/11 00:23)