作者jeunder ()
看板Prob_Solve
标题Re: [问题] ancestry problem
时间Fri Jun 22 05:11:42 2007
※ 引述《jeunder ()》之铭言：
: ※ 引述《march20 ()》之铭言：
: : 对整数 shift n bits 确实是 O(1), 但如果这颗树的高度是 100, 200,
: : (一代单传的树, 然後传 100 或 200 代就是了, 并不难造 XD)
: : 或怎更多时, 铁定不是 O(1) 可以完成的 XD
: 所以说在没有对 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
对了, 关於 shift 我没说清楚, 所以可能有人想不到.
除了给 node 编号之外, 还要记录编号的 bit 数,
如: 编号(二进位) 10110010 就是 8 bits, 101 就是 3 bits,
然後 10110010 >> (8 - 3) 等於 101 表示 101 是 10110010 的曾曾曾祖父...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.64.86.11