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
對了, 關於 shift 我沒說清楚, 所以可能有人想不到.
除了給 node 編號之外, 還要記錄編號的 bit 數,
如: 編號(二進位) 10110010 就是 8 bits, 101 就是 3 bits,
然後 10110010 >> (8 - 3) 等於 101 表示 101 是 10110010 的曾曾曾祖父...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.64.86.11
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 8 之 15 篇)：