這是一個(gè)java練習(xí)冊(cè)問題。我一直在尋找一種方法來解決但沒有成功。我們f(n) = 100n^4+ 5000n+ 3. Is f(n)∈ O(n^4)?如果是，則通過提供適當(dāng)?shù)恼某?shù)證明你的答案c和n_0。我相信答案是否定的，但我需要有關(guān)如何解決問題的指導(dǎo)。先感謝您！
2 回答
qq_笑_17
TA貢獻(xiàn)1818條經(jīng)驗(yàn) 獲得超7個(gè)贊
你可以用這種方式證明
100n^4 +5000n +3 < 5000(n^4 +n+1) 對(duì)于所有 n>1 ...(1)
5000(n^4 +n+1) < 5000(n^4 + n^4 + n^4) 對(duì)于所有 n>1 ... (2)
這意味著
100n^4 +5000n +3 < 15000(n^4) 對(duì)于所有 n>1
所以，證明 100n^4 +5000n +3 是 O(n^4)
慕神8447489
TA貢獻(xiàn)1780條經(jīng)驗(yàn) 獲得超1個(gè)贊
Let f(n) = 100n^4+ 5000n+ 3
簡(jiǎn)單地說，我們將刪除所有常量
Let f(n) = n^4+ n
我們將使用一些算法來評(píng)估：
Let f(n) = n^4+ n = n(n^3+1)
我們將繼續(xù)刪除常量
Let f(n) = n(n^3+1) = n*n^3 = n^4
所以最后
f(n)∈ O(n^4)
如果我誤解了什么，請(qǐng)通知我，我還在學(xué)習(xí)算法。
添加回答
舉報(bào)
0/150
提交
取消