[理工] 資料結構 時間複雜度

看板Grad-ProbAsk作者 (ㄏㄏ哥)時間8年前 (2018/01/17 17:48), 編輯推噓4(4推 0噓 9→)
留言13則, 5人參與, 8年前最新討論串1/3 (看更多)
兩個問題 都是是非題 disjoint-set forest , unique element,wightrule is applied那 下面這個例子會成立嗎？ 1.In the worst case, find an element in a set of size n take theta(logn) 在最糟情況find 還是可以保持趨近O(1)嗎？還有disjoint-set 有很多種find和union 那是要用哪一種來看還是，就用最好的find和union呢？ 2.The complexity of a comparison based algorithm cannot be faster than O(nlogn) 如果非comparison based algorithm 可以突破nlogn，但是如果是Best case不可以了嗎？ 像這題要考慮Best case嗎@@ ----- Sent from JPTT on my Sony D6653. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.82.135.229 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1516182494.A.3E0.html
→
01/17 17:53, 8年前 , 1F
1 worst case不是應該用沒collapse的find？ 我覺得
01/17 17:53, 1F
→
01/17 17:56, 8年前 , 2F
第二題題目是 BigO??
01/17 17:56, 2F
推
01/17 18:33, 8年前 , 3F
第一題 你用最好的find也是O(lgn)，可以翻一下筆記，他
01/17 18:33, 3F
→
01/17 18:33, 8年前 , 4F
會是alpha(n),不會是常數
01/17 18:33, 4F
→
01/17 19:45, 8年前 , 5F
n大 那是bigO沒錯 手機打字直接用O了XD
01/17 19:45, 5F
→
01/17 19:45, 8年前 , 6F
q大 嗯嗯應該是我錯了會趨近1是在壓縮過的路徑的分攤成
01/17 19:45, 6F
→
01/17 19:45, 8年前 , 7F
本才會這樣
01/17 19:45, 7F
推
01/17 20:45, 8年前 , 8F
第二題 只要題目沒講 都是指 worst case..
01/17 20:45, 8F
推
01/17 22:14, 8年前 , 9F
其實是我講錯了… 不過感覺你理解的方向是對的
01/17 22:14, 9F
→
01/17 22:14, 8年前 , 10F
他是考慮用weighting rule 所以union的方式有決定了 這
01/17 22:14, 10F
→
01/17 22:14, 8年前 , 11F
樣worst case才會是lgn
01/17 22:14, 11F
推
01/17 23:35, 8年前 , 12F
第二題如果用comparison tree看time complexity應該
01/17 23:35, 12F
→
01/17 23:35, 8年前 , 13F
是對的吧，leaf=2^height=n!
01/17 23:35, 13F
‣ 更多 ooxx5626 的文章
文章代碼(AID): #1QNnlUFW (Grad-ProbAsk)
‣ 更多 ooxx5626 的文章
文章代碼(AID): #1QNnlUFW (Grad-ProbAsk)