size优化的意义

Question

bobo 老师 关于基于size的优化这一节 有一个地方不是特别懂。
1）在union（4，9） 时，
您说数据比较少的应该指向数据比较多的节点
在合并 {8， 3， 4}与{9} 时候 我能理解，8 指向9， 他们合并成了 {9， 8，3，4}， 变得更长了
如果{8, 3, 4 …1m}已经是 一组一百万的数了， 那么我们没有size优化之前的做法只是把整个树的高度+1 而已，那么size的优化在哪？

		   8         9
           3         
           4
           .
           .
           .
           1m

2）另外，那么如果是{8，3，4} 与{ 1， 9}呢？
结果不都是一样的吗？

           8------>1
           3       9  
           4

或者

           8<------1
           3       9  
           4

"树"的深度没有变化。

Answer 1

liuyubobobo 2021-04-14 18:30:40

关键在于，基于 size 优化以后，有一组是 {8, 3, 4 …1m}，其他组都是 1 这样的极端情况高概率不会发生；

但如果真的是这种情况，是的，只看这一个操作，区别不大。但是再来 100 万组操作呢？如果不优化，就形成了一个 200 万的超长“树”。如果优化，最差情况是两个 100 万的树（再一次，大概率的，100 万次以后，根本形不成一个 100 万的数）

实际上，如果你运行这一小节的测试，应该可以很容易看到基于 size 的优化（UF3），性能是稳定优于 UF2 的：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/06-Union-Find/Course%20Code%20(C%2B%2B)/04-Optimize-by-Size/main.cpp

实际上，UF2 是可能严重退化的，为此，我写了一个新的测试的 main 函数，你可以实际运行一下：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/06-Union-Find/Course%20Code%20(C%2B%2B)/04-Optimize-by-Size/main2.cpp

然后可以根据 UF2 的逻辑，仔细理解一下，为什么这里的 UF2 这么慢？（因为此时形成的并查集就是链表）。

在我的环境下，这二者运行的差距是这样的：

继续加油！：）

• 提问者 慕工程1407147 #1

  非常感谢！