Re: [問題] ancestry problem

看板Prob_Solve作者時間17年前 (2007/06/22 05:01), 編輯推噓6(6推 0噓 1→)
留言7則, 2人參與, 最新討論串7/15 (看更多)
※ 引述《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
推
06/22 05:52, , 1F
如果你的 array 裡的東東, 大到一般的 datatype 放不下
06/22 05:52, 1F
推
06/22 05:53, , 2F
或者是你要解的題目裡, array 裡是要存 bignum 的話
06/22 05:53, 2F
推
06/22 05:53, , 3F
是的, 就像你說的那樣 @@
06/22 05:53, 3F
推
06/22 05:54, , 4F
但依照今天這個題目, 果沒規定樹的大小, 要暴是很容易的呀
06/22 05:54, 4F
推
06/22 05:54, , 5F
就用 8byte 來當整數好了, 那高度要 > 64 也不是什麼難事
06/22 05:54, 5F
推
06/22 09:56, , 6F
你的意思是 a[2000] = 10 內定會尋找2000次? :D
06/22 09:56, 6F
→
06/22 09:58, , 7F
哦哦哦,漏看了問號,抱歉,收回我的質疑
06/22 09:58, 7F
‣ 更多 jeunder 的文章
文章代碼(AID): #16UkT6Rq (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 7 之 15 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共15篇)
‣ 更多 jeunder 的文章
文章代碼(AID): #16UkT6Rq (Prob_Solve)