作者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/cn.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