作者jeunder ()
看板Prob_Solve
标题Re: [问题] ancestry problem
时间Fri Jun 22 05:01:57 2007
※ 引述《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
--
我不是故意来乱的啦 XD
因为太久没读书, 基本观念混乱中.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.64.86.11
1F：推 march20:如果你的 array 里的东东, 大到一般的 datatype 放不下 06/22 05:52
2F：推 march20:或者是你要解的题目里, array 里是要存 bignum 的话 06/22 05:53
3F：推 march20:是的, 就像你说的那样 @@ 06/22 05:53
4F：推 march20:但依照今天这个题目, 果没规定树的大小, 要暴是很容易的呀 06/22 05:54
5F：推 march20:就用 8byte 来当整数好了, 那高度要 > 64 也不是什麽难事 06/22 05:54
6F：推 ephesians:你的意思是 a[2000] = 10 内定会寻找2000次? :D 06/22 09:56
7F：→ ephesians:哦哦哦,漏看了问号,抱歉,收回我的质疑 06/22 09:58