[理工] [algo][演算][資結] 時間複雜度 , binary tree

[metalalive (想玩音樂)]

題目都是來自 I2A 3e


[binary tree]
1. http://imageshack.us/photo/my-images/854/0127j.jpg/

2. http://imageshack.us/photo/my-images/692/0128z.jpg/

3. http://imageshack.us/photo/my-images/16/0129p.jpg/

[複雜度]
1.
T(n) = 2 * T(n/4) + n^(1/2)
這題我算 theta( n ) , 但是很怪

2.
T(n) = 4 * T(n/3) + nlgn

3. true or false
  O(n^2) + theta(n^2) = theta(n^2)
  omega(n^2) + theta(n^2) = omega(n^2)
  可否請教為什麼呢?
  有爬過文 , 得到結論是兩者相加取大的
  omega + theta = omega 我可以理解
  但是 bigO + theta 為什麼不是 bigO



請教一下版上大大解法
希望可以說明解題概念
感激不盡阿!!



--
No time to pray....

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.128.126.145
推 mqazz1:複雜度第3題的第一個 我覺得很直觀= =..
→ metalalive:會嗎?我在思考一陣子...謝謝 @@
※ 編輯: metalalive      來自: 220.128.126.145      (06/24 19:32)