union如何找到二次算法？

Question

在快速查找算法的此实现中,构造函数采取N步骤union().

教师说这对于处理对象上的命令序列union来说太昂贵了,当它一次访问一个数组元素时,怎么可能是二次的呢？N^2N unionNunion

public class QuickFind
{
    private int[] id;

    public QuickFind(int N) {
        id = new int[N];
        for (int i=0; i<N; i++) {
            id[i] = i;
        }
    }

    public boolean connected(int p, int q) {
        return id[p] == id[q];
    }

    public void union(int p, int q) {
        int pid = id[p];
        int qid = id[q];

        for (int i=0; i<id.length; i++)
            if (id[i] == pid)
                id[i] = qid;
    }
}

Answer 1

每次调用union方法都需要迭代id数组,这需要O(n)时间.如果调用union方法n时间,则所需时间为n*O(n) = O(n^2).

通过使连接方法的时间复杂度更高,可以提高union方法O(1)的时间复杂度O(log n),但这只是一次操作.我相信你的教科书会详细解释这一点.