小编use*_*614的帖子

我正在学习关于数据结构和算法的课程。作者提到快速查找是 O(N^2)，这是有道理的（考虑到 N 个对象上的 N 个联合操作可能需要 N*N 个数组访问）。但是，我不明白为什么 Quick Union 会更好。似乎在最坏的情况下，一棵狭长的树，对 N 个对象进行 N 次 Find 操作也会导致 O(N^2) 但材料说它是 O(N)。

所以，一种是二次时间，一种是线性。我不确定我是否理解为什么会有差异。例子：

快速查找方法

int[] id = new int[10];

for(int i = 0; i < 10; i++)
    id[i] = i;  

// Quick find approach

int QuickFind(int p)
{
    return id[p];
}

public void Union(int p, int q)
{
    int pId = find(p);
    int qId = find(q);

    if (pId == qId)
        return;

    for (int i = 0; i < id.length; i++)
    {
        if(id[i] …