推 mqazz1:我怎麼覺得第4題答案是O(m + logn) 07/06 20:10
突然想到
mq 大 說的 O(m + lgn)
是發生在 m 次的 operation
皆針對某個 leaf 做 insert new node 的動作嗎?
※ 編輯: metalalive 來自: 124.8.74.14 (07/09 02:29)
推 mqazz1:恩 我是這樣想的 不過跟你的解答不一樣.. 07/09 21:46
推 kiwidoit:skewed的話O(m+n)可以嗎? 07/12 11:47
推 mqazz1:我考慮的應該就是skew的情況 07/13 10:27
→ mqazz1:不知道我有沒有誤解題意 我覺得樹高原本就O(logn) 07/13 10:28
→ mqazz1:node的value值照遞增或遞減的順序insert..好像是O(m+lgn) 07/13 10:29
→ mqazz1:不知k大的O(m+n)是怎麼來的? 07/13 10:29
推 kiwidoit:我是說如果他題目沒講樹高O(logn)，應該就是O(m+n吧)@@? 07/13 11:00
推 mqazz1:原來是這意思 它題目確實沒說已有幾個node 07/13 11:09
→ mqazz1:只說做m個operation 這樣skew的情況應該就解答的O(m) 07/13 11:10
推 kiwidoit:yes~~ 07/13 13:15