动态连通性问题union方法的大O

Question

我分析这个函数遇到了一个悖论，为什么这个函数的时间复杂度是N^2而不是N？

public void union(int a, int b) {
        int aid = ids[a];
        int bid = ids[b];
        for (int i = 0; i < ids.length; i++) {
            if (ids[i] == aid) {
                ids[i] = bid;
            }
        }
    }

是eager approach的实现，解决动态连接问题，完整代码为：

// Union method has N^2 time complexity!!
class EagerApproach extends UnionFind {


    protected int[] ids;

    EagerApproach(int[] input) {
        super(input);
        ids = new int[input.length];
        System.arraycopy(input, 0, ids, 0, input.length);
    }


    public boolean connected(int a, int b) {
        return ids[a] == ids[b];
    }

    public void union(int a, int b) {
        int aid = ids[a];
        int bid = ids[b];
        for (int i = 0; i < ids.length; i++) {
            if (ids[i] == aid) {
                ids[i] = bid;
            }
        }
    }

    public int[] getIds() {
        return ids;
    }
}

Answer 1

如果您的数组访问 ids[x] 是常数时间 O(1)，union 方法的时间复杂度是数组长度的线性 ids。所以

O(ids.length)

或O(n) 如果我们将n定义为ids.length.

注意 n 和 ids 的定义。如果在您的特定应用程序中，n 被定义为 ids.length = n * n，那么这显然是 O(n^2)，而 n 是 sqrt(ids.length)。

动态连通性问题union方法的大O

Big O of union method of dynamic connectivity problem

algorithm

big-o

time-complexity

data-structures