Re: [理工] [ds]-複雜度
※ 引述《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
推
03/23 18:16, , 1F
03/23 18:16, 1F
推
03/23 18:25, , 2F
03/23 18:25, 2F
→
03/23 18:25, , 3F
03/23 18:25, 3F