Re: [問題] ancestry problem

看板Prob_Solve作者march20時間17年前 (2007/06/21 07:45)推噓11(11推 0噓 1→)

留言12則, 3人參與討論串6/15 (看更多)

※ 引述《jeunder ()》之銘言： : 標題: Re: [問題] ancestry problem : 時間: Thu Jun 21 00:26:50 2007 : : 來點直覺的想法吧~ : : 對 node 編號, 從 root 開始, 由上至下, 由左至右, 編號: 1, 2, 3, ... : 如果 tree 不是 complete, 那麼空的 node 也要給編號. : : 你會發現父子關係是... : 父親編號往左 shift 1 bit 等於左兒子編號, 再加 1 就是右兒子. : : 所以... (剩下你自己想 XD) : : 推 hardcover:thanks, 你這樣好像也要 logn 06/21 00:30 我想原 jeunder 是想這樣做的先跑一次對全部的 node 做編號, 這是 O(n) (DFS 即可, 所以時間複雜度是 O(|V| + |E|), 因為是 binary tree, 所以是 O(|V|) , 也就是 O(n)) 每個node 的編號就是該 node 同高度的 full binary 裡的編號 (想像沒有長出來的 node 編號是空的. 不過要注意, 這些空的 node 並沒真的去 visit) : 推 jeunder:有點困惑 (太久沒唸書了XD) 請問對整數 shift n bits (一 06/21 00:58 : → jeunder:次做完) 算是 O(1) 還是 O(n) ??? 06/21 01:01 : 推 ephesians:這只有找直接的節點才是O(1),距離遠一點就是O(logn) 06/21 01:23 不是 O(1) 也不是 O(log n), 其實是 O(n) @@ 對整數 shift n bits 確實是 O(1), 但如果這顆樹的高度是 100, 200, (一代單傳的樹, 然後傳 100 或 200 代就是了, 並不難造 XD) 或怎更多時, 鐵定不是 O(1) 可以完成的 XD -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 128.54.49.35 ※ 編輯: march20 來自: 128.54.49.35 (06/21 07:45) ※ 編輯: march20 來自: 128.54.49.35 (06/21 07:46)

推

TonyQ

06/21 12:20, , 1^F

06/21 12:20, 1^F

→

TonyQ

06/21 12:21, , 2^F

06/21 12:21, 2^F

推

ephesians

06/21 13:24, , 3^F

06/21 13:24, 3^F