size优化的意义
来源：6-4 基于size的优化
慕工程1407147
2021-04-14
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
"树"的深度没有变化。
1回答
-
关键在于，基于 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 这么慢？（因为此时形成的并查集就是链表）。
在我的环境下，这二者运行的差距是这样的：
继续加油！：）
012021-04-15
相似问题