[理工]資結觀念一問

看板Grad-ProbAsk作者 (O_O)時間7年前 (2017/02/04 11:48), 7年前編輯推噓8(8推 0噓 15→)
留言23則, 7人參與, 最新討論串1/1
http://i.imgur.com/0wNqjKL.jpg
對於以下兩個複雜度，不太理解緣由，跪求解釋 1.search kth item in AVL tree =O(logn) 不是很理解此處要如何以logn搜得 2.output all data elements in order in singly linked-list =O(n) 也不是很懂，我想到最快的方法是先全output再排序，要O(nlogn) 感謝大家，剩不多天了，加油！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.94.109 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486180080.A.958.html ※ 編輯: ssssIssss (140.112.94.109), 02/04/2017 11:48:45
推
02/04 11:57, , 1F
第二題應該是已經假設linked-list已經sorted好，再outpu
02/04 11:57, 1F
→
02/04 11:57, , 2F
t出來，才會是O(n)
02/04 11:57, 2F
考場上，遇到都要預先假設sorted？
推
02/04 12:20, , 3F
avl高度logn搜尋走到葉子最多也是logn次比較
02/04 12:20, 3F
是的，不過kth的話，應該要在每個node上附上他擁有的左子樹的node樹以供判斷，所以 我覺得O(logn)不太能理解@@ ※ 編輯: ssssIssss (140.112.94.109), 02/04/2017 12:25:22
推
02/04 12:22, , 4F
每個點都記說比自己小的有幾個 可以在logn統計出來 更
02/04 12:22, 4F
→
02/04 12:22, , 5F
新只要常數
02/04 12:22, 5F
是分攤的概念嗎？在建樹的時候每次都順便花常數時間記下比自己小的（像是在insert n ew node時路過便更新），然後search時就只要花費O(logn)找出k便可？ ※ 編輯: ssssIssss (140.112.94.109), 02/04/2017 12:29:13
推
02/04 12:32, , 6F
我是會假設已經sorted好欸，因為課本上也是寫O(n) //沒
02/04 12:32, 6F
→
02/04 12:32, , 7F
記錯的話
02/04 12:32, 7F
如同遇到linked-list的insert和delete一樣，直接假設已經的得到前一個node，所以只 需O(1)嗎，懂了！ ※ 編輯: ssssIssss (223.136.98.91), 02/04/2017 12:45:20
推
02/04 15:03, , 8F
沒錯～
02/04 15:03, 8F
→
02/04 16:06, , 9F
第一題可以google augmented bst 在建樹時要先記錄一些值
02/04 16:06, 9F
推
02/04 16:48, , 10F
AVL TREE本身就是 Binary Search tree 所以對他做中序巡防
02/04 16:48, 10F
→
02/04 16:48, , 11F
就可以照順序印出來了
02/04 16:48, 11F
推
02/04 16:54, , 12F
回錯了 sorry QQ
02/04 16:54, 12F
→
02/04 17:07, , 13F
1:你要找第k個，先算root的樹高，比k大就去左子樹找，
02/04 17:07, 13F
→
02/04 17:07, , 14F
比k小去右子樹找k-高，如此遞迴，你每次的成本就是在算
02/04 17:07, 14F
→
02/04 17:07, , 15F
樹高=O(nlogn)
02/04 17:07, 15F
→
02/04 17:10, , 16F
打錯，每次算樹高=(logn)
02/04 17:10, 16F
→
02/04 17:21, , 17F
應該不用到 augmenting BST 只是search而已
02/04 17:21, 17F
→
02/04 17:31, , 18F
augmenting BST 主要目的在 find min or max 可以不
02/04 17:31, 18F
→
02/04 17:32, , 19F
用到 logn
02/04 17:32, 19F
推
02/04 21:55, , 20F
不用 augmenting BST 要怎樣在O(lg n)時間內找到第 k 大？
02/04 21:55, 20F
→
02/04 22:03, , 21F
不是問 K th 嗎@@? 還是我理解有誤
02/04 22:03, 21F
是問kth沒錯喔！ 我找到解法了，它命名為Augmented tree data structure，不知道跟你們說的Augmented BST是否一樣 作法如下：建樹時，順便記錄自己左子樹的node數（假設為n）。在做search kth時，確 定root，若k=n+1則得解為root，若k<n+1則往左走、k>n+1則往右。最多走tree的高。 複雜度為O(logn) ※ 編輯: ssssIssss (140.112.94.109), 02/05/2017 10:40:28
→
02/05 10:59, , 22F
我重新看了一次argument data structure , AA大說的
02/05 10:59, 22F
→
02/05 10:59, , 23F
沒錯 是我觀念有誤
02/05 10:59, 23F
考前多得到一個觀念就是賺啊！XD ※ 編輯: ssssIssss (140.112.94.109), 02/05/2017 11:32:13
‣ 更多 ssssIssss 的文章
文章代碼(AID): #1ObKxmbO (Grad-ProbAsk)