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

Question

我正在 LeetCode 上解决 a problem：

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time. So for nums = [100,4,200,1,3,2], the output is 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) 所声称的吗许多答案，例如 this one?我的理解是Union Find是一个O(NlogN)的算法。

他们说得对吗？或者，我错过了什么吗？

Answer 1

他们是对的。 path compression 和 union by rank 的正确实现的 Union Find 总体上具有线性运行时间复杂度，而任何单独的操作都有摊销常数运行时间复杂度。任何类型的 m 运算中的 The exact complexity 是 O(m * alpha(n))，其中 alpha 是反阿克曼函数。对于物理世界中任何可能的n，反阿克曼函数都不超过4。因此，我们可以说单个操作是常数，算法整体是线性的。

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

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

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

return find(parent[i])

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

此处按等级合并很明显：

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

确保子节点多的节点成为子节点少的节点的根。因此，更少的节点需要重新分配一个新的父节点，因此工作更少。

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

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

Is this Union Find really O(n) as they claim?

c++

algorithm

disjoint-sets

union-find