Re: [理工] [algo][演算][資結] 時間複雜度 , bina …

[mqazz1 (無法顯示)]

※ 引述《metalalive (想玩音樂)》之銘言：
: 題目都是來自 I2A 3e
: [複雜度]
: 1.
: T(n) = 2 * T(n/4) + n^(1/2)
: 這題我算 theta( n ) , 但是很怪

a=2, b=4, n^(log_4(2)) = n^(1/2)

用master解

O( n^(1/2) logn )


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

這題可以用master解

a=4, b=3, n^(log_4(3)) > nlgn

=> O(n^(log_4(3))

                                       2   2
ps. T(n) = 4T(n/2) + (n^2)logn 會是O( n log n )



: 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

你得到的結論相加取大的

O(n^2) 是upper bound  =>  想成小於等於n^2

theta(n^2) 是tight bound => 想成等於n^2

當然是theta(n^2)比較大

=========================================

omega(n^2) 是lower bound => 想成大於等於n^2

theta(n^2) 是tight bound => 想成等於n^2

所以omega(n^2)比較大


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

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.33.154
※ 編輯: mqazz1          來自: 140.118.33.154       (06/23 17:27)
→ mqazz1:不知道有沒有什麼地方出錯
→ mqazz1:因為手上沒有書 比較沒辦法驗證我的過程...
推 da0910cc:威哥
= =
推 FRAXIS:第一題不能用Master Theorem嘛？
感謝F大指點
※ 編輯: mqazz1          來自: 61.228.27.114        (06/23 20:41)
推 metalalive:謝謝 mqazz 大 ! 第一題我鬼打牆了,展開後確實是
→ metalalive:O( n^(1/2) * logn )