Re: [問題] ancestry problem
看板Prob_Solve (計算數學 Problem Solving)作者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)
推
06/21 12:20, , 1F
06/21 12:20, 1F
→
06/21 12:21, , 2F
06/21 12:21, 2F
推
06/21 13:24, , 3F
06/21 13:24, 3F
推
06/21 14:52, , 4F
06/21 14:52, 4F
推
06/21 14:53, , 5F
06/21 14:53, 5F
推
06/21 14:53, , 6F
06/21 14:53, 6F
推
06/21 14:54, , 7F
06/21 14:54, 7F
推
06/21 14:55, , 8F
06/21 14:55, 8F
推
06/21 14:56, , 9F
06/21 14:56, 9F
推
06/21 14:58, , 10F
06/21 14:58, 10F
推
06/21 14:59, , 11F
06/21 14:59, 11F
推
06/21 17:48, , 12F
06/21 17:48, 12F
※ 編輯: march20 來自: 71.136.243.18 (06/22 16:52)
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
