推 flyguava:所以是要怪題目囉XD 03/23 18:16
推 assassin88:我剛重新看了一下 應該是 tight bound 沒錯 .. 口誤 XD 03/23 18:25
→ assassin88:而你的第二題應該是 true 03/23 18:25
※ 引述《flyguava (紅芭樂)》之銘言：
: If T(n) = T(n/2) + cn, then T(n)= O (nlogn)
: 請問該選T 還 F ?
: 謝謝
這篇的推文討論的很詭異...科科
所謂的 c 指的就是 constant 常數
並不會受到 n 的影響
T(n) = T(n/2) + cn = cn ( 1 + 1/2 + 1/4 + .... ) = θ(n)
之所以是 False 是因為想取 tight upper bound 吧
這類題目常常寫不清楚
但絕對不會是 c = n^x 這種東西的關係...
--
人家可不是為了你才這樣做的哦!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.198.35.85