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