[演算法] 時間複雜度

看板Math作者 (無法顯示)時間15年前 (2011/02/06 23:28), 編輯推噓2(2推 0噓 10→)
留言12則, 3人參與, 最新討論串1/1
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
推
02/06 23:32, , 1F
true true true .........吧! 一眼看過去直觀是這樣
02/06 23:32, 1F
→
02/06 23:34, , 2F
我是試著把數字帶進去呀~ O() 是Upper bound
02/06 23:34, 2F
→
02/06 23:36, , 3F
所以 n^2 + n^3 = O(n^4)
02/06 23:36, 3F
→
02/06 23:36, , 4F
n^2*n^3 = n^5 = O(n^5) 這是符合的 因為你已經帶入
02/06 23:36, 4F
→
02/06 23:37, , 5F
bigO裡面最大的數 不會有例外產生 So It's for all
02/06 23:37, 5F
→
02/06 23:38, , 6F
第三題 全部把左邊BigO 除掉 做Log 會變成
02/06 23:38, 6F
→
02/06 23:39, , 7F
lgn^2 和 2^n 取log 變成 nlog2 => nlog2 > lgn^2
02/06 23:39, 7F
→
02/06 23:40, , 8F
所以一定符合第三題的all case
02/06 23:40, 8F
→
02/06 23:40, , 9F
第一次解題 不對的地方 請版眾 和 大大們指教@@"
02/06 23:40, 9F
→
02/06 23:41, , 10F
我想應該有更合理的解釋~
02/06 23:41, 10F
推
02/07 00:18, , 11F
想要請問你們有需要用嚴謹的 big-O 定義證明嗎?
02/07 00:18, 11F
→
02/07 00:19, , 12F
直觀上都是對的沒有錯.
02/07 00:19, 12F
‣ 更多 mqazz1 的文章
文章代碼(AID): #1DJhuYfO (Math)