[理工] [DS] AVLTree 時間複雜度問題

看板Grad-ProbAsk作者 (逆宇)時間13年前 (2012/07/04 23:23), 編輯推噓3(3推 0噓 7→)
留言10則, 4人參與, 最新討論串1/1
AVL Tree 的操作 找到第K個item(由小到大算過來第K個) 的時間是 O(logn) 想不太通原因 如果是先用inorder把全部的東西由小到大dump出來 然後再去找第K個 這樣子的話時間應該是 O(n) --> n個node dump出來的時間 但是為甚麼書上 跟 洪逸上課教的時候 都是說 O(logn) 想了一個晚上想不通@@ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.166.53.3 ※ 編輯: mingcloud 來自: 118.166.53.3 (07/04 23:25)
推
07/04 23:44, , 1F
樹的高度不是log n?
07/04 23:44, 1F
→
07/04 23:50, , 2F
阿 我知道樹的高度是logn 但是樹高 跟 找到由小到大第K
07/04 23:50, 2F
→
07/04 23:50, , 3F
個item 的關係是在?
07/04 23:50, 3F
推
07/05 07:37, , 4F
他是假設Tree中每個節點存有其子樹所含節點個數
07/05 07:37, 4F
→
07/05 07:37, , 5F
有子樹節點數目的資訊的話，就可以O(lg n)的時間內解決..
07/05 07:37, 5F
→
07/05 10:05, , 6F
喔喔 好 感謝樓上大大的解說...原來有這個前提不知道
07/05 10:05, 6F
→
07/05 10:06, , 7F
不過感覺他那個表格很多前提都沒有說得很清楚...
07/05 10:06, 7F
推
07/07 15:20, , 8F
程式不會是這樣跑的(全部丟出來再挑) >>這樣是O(N)
07/07 15:20, 8F
→
07/07 15:20, , 9F
但實際上不是這樣跑的;AVL是完整樹;用陣列儲存
07/07 15:20, 9F
→
07/07 15:21, , 10F
但是在跑AVL時不會是sequence
07/07 15:21, 10F
‣ 更多 mingcloud 的文章
文章代碼(AID): #1Fz5_YI8 (Grad-ProbAsk)