Re: [問題] ancestry problem

[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

--
我不是故意來亂的啦 XD
因為太久沒讀書, 基本觀念混亂中.

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.64.86.11
推 march20:如果你的 array 裡的東東, 大到一般的 datatype 放不下
推 march20:或者是你要解的題目裡, array 裡是要存 bignum 的話
推 march20:是的, 就像你說的那樣 @@
推 march20:但依照今天這個題目, 果沒規定樹的大小, 要暴是很容易的呀
推 march20:就用 8byte 來當整數好了, 那高度要 > 64 也不是什麼難事
推 ephesians:你的意思是 a[2000] = 10 內定會尋找2000次? :D
→ ephesians:哦哦哦,漏看了問號,抱歉,收回我的質疑