作者mqazz1 (無法顯示)
看板Math
標題[演算法] 時間複雜度
時間Sun Feb 6 23:28:32 2011
ture or false
1. O(n^2) + O(n^3) = O(n^4)
2. O(n^2) * O(n^3) = O(n^5)
3. O(n) ^ O(lgn) = O(2^n)
請問這幾題要怎麼判斷呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.24.214
1F：推 jameschou :true true true .........吧! 一眼看過去直觀是這樣 02/06 23:32
2F：→ charliejack :我是試著把數字帶進去呀~ O() 是Upper bound 02/06 23:34
3F：→ charliejack :所以 n^2 + n^3 = O(n^4) 02/06 23:36
4F：→ charliejack :n^2*n^3 = n^5 = O(n^5) 這是符合的 因為你已經帶入 02/06 23:36
5F：→ charliejack :bigO裡面最大的數 不會有例外產生 So It's for all 02/06 23:37
6F：→ charliejack :第三題 全部把左邊BigO 除掉 做Log 會變成 02/06 23:38
7F：→ charliejack :lgn^2 和 2^n 取log 變成 nlog2 => nlog2 > lgn^2 02/06 23:39
8F：→ charliejack :所以一定符合第三題的all case 02/06 23:40
9F：→ charliejack :第一次解題 不對的地方 請版眾 和 大大們指教@@" 02/06 23:40
10F：→ charliejack :我想應該有更合理的解釋~ 02/06 23:41
11F：推 hcsoso :想要請問你們有需要用嚴謹的 big-O 定義證明嗎? 02/07 00:18
12F：→ hcsoso :直觀上都是對的沒有錯. 02/07 00:19