楼主:
aa40105 (H.K.K)
2014-12-24 15:53:124.Union/Find operation: Show that a tree obtained by applying the
weighting rule for Union is bounded above by O(log n).
我看到98年交大资联的题目
http://i.imgur.com/lqUZ8S8.jpg
http://i.imgur.com/yGbYogn.jpg
103这题是指画出上面那棵树那样吗?
还是写说哪种树符合题目所描述的意思??
我不太懂要如何写这题
我猜是要证根据union weight rule建立出来的树高度(搜寻成本)=O(log n)
Union by weighting rule_K子树接P点为新ROOTCollaping rule(compression)_沿X寻找的node改指向root
我的想法是b-tree是union by weight的worst case,而b-tree高度是log n来当上界,没完整严谨思考,提出来讨论。
作者: DiAdo (DiAdo) 2014-12-27 12:55:00
这题应该只是要我们做一次union和find就结束了吧证明树高的话应该可以用node数量做强归纳法,但这不是原题的题意
其实我没搞懂原po要问的是文字叙述的那题还是图片的
作者:
JoJo56 (JoJO)
2014-12-28 16:48:00我是写说Binomail Heap in worst case合并时间O(1)最多有logN棵树 所以为logN
看到楼上推文我发现我上面推错了,*b-tree -> binomial tree
作者:
JacobSyu (JacobSyu)
2014-12-30 11:23:00这题果断放弃...考amortization algo?(配分9分,)照JoJo感觉可能有点笔墨分数XD 看教授了..
作者:
FRAXIS (喔喔)
2014-12-30 20:57:00