作者chiron127 (黑潮)
看板Math
標題[代數] Big-O的推導過程問題
時間Thu Nov 10 23:03:24 2011
我的數學底子很不好,所以不確定這算「代數」問題還是「其他」
手邊有一題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))
推導:
Step1 → 2n^2+9n+10 <= C ﹡n^2
取C=3
Step2 → n^2-9n-10 >= 0
Step3 → (n-10)(n+1) >= 0
Step4 → n <= -1 或 n >= 10
…
一直搞不懂
Step1如何變到Step2?
Step2如何變到Step3(不確定是不是用因式分解之類的公式?)
請知道如何解的高手告知解法(為什麼?)非常感謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.229.111
推 jacky7987 :移項 十字交乘 11/10 23:07
推 hijamoya :1=>2只是把左邊都移到右邊而已 2=>3 只是用十字交乘 11/10 23:26
→ hijamoya :第4就是答案= =解答都寫出來了 11/10 23:26
→ chiron127 :謝謝jacky7987跟hijamoya 11/10 23:47
→ chiron127 :移項加十字交乘已可算出。但step是不是應該n>=-1或10 11/10 23:50
推 asilzheng :在n<=-1或n>=10的範圍中 會使n+1與n-10為同負或同正 11/11 00:29