动态连接问题的联合方法的大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;
}
}
}

它采用一种实现急切的方法，解决动态连接问题，完整的代码是：

// 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，那么这显然与nsqrt(ids.length)O(n^2)。