※ 引述《ledia ()》之銘言：
: ※ 引述《jeunder ()》之銘言：
: : 所以說在沒有對 array 做 preprocessing (例如: sorting...) 的情況下
: : 要在 array 裡面 search 某個東西... 是 O(nlogn) 囉? XD
: : 怎麼說? 因為對 array 裡面的項目定址需要用到 O(logn) 個 bits,
: : 而依序 search n 個項目, 每次都要對位址做 O(logn) bits 的加法,
: : 所以 array search 是 O(nlogn) ?
: : 按照你的說法, 如果 array 裡面的元素數量是一兆, 兩兆或更多時,
: : 位址的運算鐵定不是 O(1) 可以完成的 XD
: 這也就是為什麼很多 complexity/algorithm 的書籍
: 開宗明義會先說清楚他們在什麼 model 上討論問題
: 像是許多書用的就是 random access machine (RAM) model
: RAM model 的其中一個條件就是
: * Each memory access takes exactly one time step, and we have as
: much memory as we need. The RAM model takes no notice of whether
: an item is in cache or on the disk, which simplifies the analysis.
: 巧妙的躲開了定址所需要的 O(logn) 的問題
: 但是 shift logn bits 仍然是用 loop 做出來的
: 則應該還是需要花 O(logn) 的時間
我在看這篇文章的時候,完全同意大大的說法
可是在我看mit press(introduction to algorithms)
裡面chapter2的p 22裡面提到
many computers have a "shift left" instruction , which
in constant time shifts the bits of an integer by k position
to the left.
我在想是不是因為在白算盤一書裡面.雖然 divide 也要做不只一次的運算
(在電路裡)
可是可以在constant（記得是四個） 的 cycle數中做完
就跟這邊的shift指令一樣.
所以mips的指令我們都視為是constant time(推廣至assembly)
感謝各位大大指導<(__)>
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.225.198.46