请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

基于size优化和基于rank优化的对比

图片描述
如果采用基于size的优化, 4->3->8是不可能的吧, 基于size优化后三个元素应该是
a -> c <- b的形式吧

基于size优化后,对于森林中的每棵树,当树的节点数size>=3时,这棵树是不会退化为链表形式的吧,每棵树都会有几个分叉吧。

有一点不是太理解
基于size优化是不是因为
假设:树a的结点数 > 树b的结点数,也就意味着树a的深度“很大概率”上比树b的深度要大(应该不是100%,但是我举不出来反例,求bobo老师举个例子),所以将结点数少的集合并入到结点数多的集合。

所以基于size优化和基于rank优化的时间上,rank略小于size吧,因为size不是100%判定正确的,也可能深度大的树并到了深度小的树。

正在回答

1回答

liuyubobobo 2019-10-09 14:53:07

1)你是对的,不可能。这里只是举例,说明一下这个 size 的含义,我没有用代码重头模拟这个形成过程。抱歉。


2)你的理解是对的。基于 size 的优化是走向基于 rank 的优化的一个思维过渡。实际上,并查集的标准优化形式是基于 rank 的优化。


继续加油!:)

0 回复 有任何疑惑可以回复我~
  • 我也思考了这个问题,仍然没有想到size优化下的UF会出现大树更浅,小树更深的场景,还请老师指导一下。
    而且我在别的提问中有看到测试出size优于rank的场景,如果抛去jvm、环境等影响不讨论,我想他们之间的性能差异,可能在于:rank多一次比较,而size多一些sz的维护吧?
    回复 有任何疑惑可以回复我~ 2020-05-02 20:37:36
  • 一个节点下10000个节点,只有两层;100个节点深度排列,就有100层。前者大树更浅;后者小树更深。
    回复 有任何疑惑可以回复我~ 2020-05-03 02:19:15
问题已解决,确定采纳
还有疑问,暂不采纳
意见反馈 帮助中心 APP下载
官方微信