这个 Union Find 真的像他们声称的那样 O(n) 吗？

Question

我正在LeetCode上解决一个问题：

给定一个未排序的整数数组nums，返回最长连续元素序列的长度。您必须编写一个及时运行的算法O(n)。因此对于nums= [100,4,200,1,3,2]，输出为4。

解决这个问题的Union Find解决方案如下：

class Solution {
public:
    vector<int> parent, sz;
    
    int find(int i) {
        if(parent[i]==i) return i;
        return parent[i]=find(parent[i]);
    }
    
    void merge(int i, int j) {
        int p1=find(i);
        int p2=find(j);
        
        if(p1==p2) return;
        if(sz[p1]>sz[p2]) {
            sz[p1]+=sz[p2];
            parent[p2]=p1;
        } else {
            sz[p2]+=sz[p1];
            parent[p1]=p2;
        }
    }

    int longestConsecutive(vector<int>& nums) {
        sz.resize(nums.size(),1);
        parent.resize(nums.size(),0);

        iota(begin(parent),end(parent),0);

        unordered_map<int, int> m;

        for(int i=0; i<nums.size(); i++) {
            int n=nums[i];
            if(m.count(n)) continue;
            if(m.count(n-1)) merge(i,m[n-1]);
            if(m.count(n+1)) merge(i,m[n+1]);
            m[n]=i;
        }

        int res=0;
        for(int i=0; i<parent.size(); i++) {
            if(parent[i]==i && sz[i]>res) {
                res=sz[i];
            }
        }

        return res;
    }
};

OJ 接受了这一点（运行时：80毫秒，比最长连续序列的 C++ 在线提交更快76.03%），但这真的O(n)像许多答案所声称的那样吗？我的理解是Union Find是一个O(NlogN)算法。

他们是对的吗？或者，我错过了什么吗？

Answer 1

他们是对的。正确实现的并集查找（具有路径压缩和按等级并集）总体上具有线性运行时间复杂度，而任何单个操作都具有摊销恒定运行时间复杂度。任何类型的操作的确切复杂度是逆阿克曼函数。对于物理世界中任何可能的情况，阿克曼反函数不超过 4。因此，我们可以说各个操作是常数，算法整体是线性的。mO(m * alpha(n))alphan

代码中路径压缩的关键部分在这里：

return parent[i]=find(parent[i])

与以下不使用路径压缩的情况相比：

return find(parent[i])

这部分代码的作用是扁平化层次结构中的节点结构，并将每个节点直接链接到最终的根。只有在第一次运行时，find您才会遍历整个结构。下次您将获得直接命中，因为您将节点的父节点设置为其最终根。请注意，第二个代码片段工作得很好，但当您对路径本身不感兴趣而只对最终根感兴趣时，它只会执行多余的工作。

等级联盟在这里显而易见：

if(sz[p1]>sz[p2]) {...

它确保具有较多子节点的节点成为具有较少子节点的节点的根。因此，需要重新分配新父节点的节点较少，因此工作量也较少。

注意：以上内容已根据@Matt-Timmermans 和@kcsquared 的反馈进行了更新和更正。