PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] ancestry problem

看板Prob_Solve (計算數學 Problem Solving)作者king19880326 (OK的啦～我都可以接受)時間16年前 (2009/01/31 20:05)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串15/15 (看更多)

※ 引述《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