[演算法] 時間複雜度

[mqazz1 (無法顯示)]

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
推 jameschou   :true true true .........吧! 一眼看過去直觀是這樣
→ charliejack :我是試著把數字帶進去呀~ O() 是Upper bound
→ charliejack :所以 n^2 + n^3 = O(n^4)
→ charliejack :n^2*n^3 = n^5 = O(n^5) 這是符合的 因為你已經帶入
→ charliejack :bigO裡面最大的數 不會有例外產生 So It's for all
→ charliejack :第三題 全部把左邊BigO 除掉 做Log 會變成
→ charliejack :lgn^2 和 2^n 取log 變成 nlog2 => nlog2 > lgn^2
→ charliejack :所以一定符合第三題的all case
→ charliejack :第一次解題  不對的地方 請版眾 和 大大們指教@@"
→ charliejack :我想應該有更合理的解釋~
推 hcsoso      :想要請問你們有需要用嚴謹的 big-O 定義證明嗎?
→ hcsoso      :直觀上都是對的沒有錯.