V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Higurashi
V2EX  ›  问与答

并查集算法的最坏情况

  •  
  •   Higurashi · 2022-03-14 21:42:21 +08:00 · 1280 次点击
    这是一个创建于 985 天前的主题,其中的信息可能已经有所发展或是发生改变。

    并查集问题中,有一种按树大小(节点总数)合并树的算法。也就是用数组写树,合并两棵树时总是将小树(节点总数较小的树)的根节点连接到大树的根节点上。

    该算法的一个性质是,其构造的森林中的任意节点的深度最多为 lgN 。

    我不清楚为什么它的最坏情况是不断合并节点总数相同的两颗树,比如 2-2 (合并节点总数都为 2 的两棵树)、4-4 、8-8... 想着是因为树的深度越大,find 操作可能的最坏情况就越耗时,然而,一颗不平衡的二叉树难道不比平衡的二叉树有更差的最坏情况吗?

    不知道该怎样理解?谢谢。

    4 条回复    2022-03-15 19:21:47 +08:00
    sengxian
        1
    sengxian  
       2022-03-14 22:14:26 +08:00
    首先不是按照节点数量,而是按照深度启发式合并;其次你的问题的答案是:如果每次合并的树深度不一样,那么合成新树的深度并不会改变,也就不影响最坏情况
    Higurashi
        2
    Higurashi  
    OP
       2022-03-14 22:38:29 +08:00
    @sengxian #1 感谢回复。是的,更常见的似乎的确是按高度合并,但按大小合并也是一种可行(而且效率同样较高)的方法。我知道在该情况下深度不变,但这一点如何真正说明连续合并两棵树大小相等时是最坏的?能给些更详细些的提示吗?
    sengxian
        3
    sengxian  
       2022-03-15 16:54:16 +08:00
    Higurashi
        4
    Higurashi  
    OP
       2022-03-15 19:21:47 +08:00
    @sengxian #3 虽然没有细看,也没有看懂,但知道这是在作均摊分析,似乎并没有直接分析“最坏”情形。但是在 https://oi-wiki.org/ds/dsu/ 的引用中,有一篇论文( https://www.researchgate.net/publication/220430653_Worst-case_Analysis_of_Set_Union_Algorithms/link/0a85e53cd28bfdf5eb000000/download )对此进行了分析,这篇论文中应该有想要的答案。显然对这个问题的解释并不是一两句话所能够说清楚的,有一种直观的理解方法当然最好,没有的话问题就到此为止。谢谢。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2778 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 07:07 · PVG 15:07 · LAX 23:07 · JFK 02:07
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.