作者ooxx5626 (ㄏㄏ哥)
看板Grad-ProbAsk
標題[理工] 資料結構 時間複雜度
時間Wed Jan 17 17:48:11 2018
兩個問題 都是是非題
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1516182494.A.3E0.html
1F：→ nova06091: 1 worst case不是應該用沒collapse的find？ 我覺得 01/17 17:53
2F：→ nova06091: 第二題題目是 BigO?? 01/17 17:56
3F：推 q1qip123: 第一題 你用最好的find也是O(lgn)，可以翻一下筆記，他 01/17 18:33
4F：→ q1qip123: 會是alpha(n),不會是常數 01/17 18:33
5F：→ ooxx5626: n大 那是bigO沒錯 手機打字直接用O了XD 01/17 19:45
6F：→ ooxx5626: q大 嗯嗯應該是我錯了會趨近1是在壓縮過的路徑的分攤成 01/17 19:45
7F：→ ooxx5626: 本才會這樣 01/17 19:45
8F：推 FRAXIS: 第二題 只要題目沒講 都是指 worst case.. 01/17 20:45
9F：推 q1qip123: 其實是我講錯了… 不過感覺你理解的方向是對的 01/17 22:14
10F：→ q1qip123: 他是考慮用weighting rule 所以union的方式有決定了 這 01/17 22:14
11F：→ q1qip123: 樣worst case才會是lgn 01/17 22:14
12F：推 tung3567752: 第二題如果用comparison tree看time complexity應該 01/17 23:35
13F：→ tung3567752: 是對的吧，leaf=2^height=n! 01/17 23:35