我正在上有关数据结构和算法的类(class)。作者提到快速查找是O(N ^ 2),这很有意义(假设对N个对象进行N个联合操作可能需要N * N个数组访问)。但是,我不明白为什么Quick Union会更好。在最坏的情况下,似乎是一棵长而狭窄的树,对N个对象进行N个查找操作也将导致O(N ^ 2),但是 Material 说它是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] == pId)
id[i] = qId;
}
}
快速联合方法
int Find(int p)
{
while(p != id[p])
p = id[p];
return p;
}
void QuickUnion(int p, int q)
{
int pRoot = Find(p);
int qRoot = Find(q);
if(pRoot == qRoot)
return;
id[pRoot] = qRoot;
}
最佳答案
// Naive implementation of find
int find(int parent[], int i)
{
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
// Naive implementation of union()
void Union(int parent[], int x, int y)
{
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
上面的
union()
和find()
天真,最坏的情况下时间复杂度是线性的。创建的代表子集的树可能会倾斜,并且可能变得像链表一样。以下是最坏情况的示例。Let there be 4 elements 0, 1, 2, 3
Initially all elements are single element subsets.
0 1 2 3
Do Union(0, 1)
1 2 3
/
0
Do Union(1, 2)
2 3
/
1
/
0
Do Union(2, 3)
3
/
2
/
1
/
0
在最坏的情况下,可以将上述操作优化为
O(Log n)
。想法是始终将较小的深度树附加在较深树的根下。这项技术被称为,称为联合。术语“等级”而不是“高度”是优选的,因为如果使用路径压缩技术(我已在下面进行了讨论),那么等级并不总是等于“高度”。Let us see the above example with union by rank
Initially all elements are single element subsets.
0 1 2 3
Do Union(0, 1)
1 2 3
/
0
Do Union(1, 2)
1 3
/ \
0 2
Do Union(2, 3)
1
/ | \
0 2 3
天真的方法的第二个优化是路径压缩。想法是在调用
find()
时将树展平。当为元素find()
调用x
时,返回树的根。 find()
操作从x
向上遍历以找到根。路径压缩的想法是使找到的根成为x
的父级,这样我们就不必再次遍历所有中间节点。如果x
是子树的根,则x
下所有节点的路径(到根)也会压缩。Let the subset {0, 1, .. 9} be represented as below and find() is called
for element 3.
9
/ | \
4 5 6
/ \ / \
0 3 7 8
/ \
1 2
When find() is called for 3, we traverse up and find 9 as representative
of this subset. With path compression, we also make 3 as child of 9 so
that when find() is called next time for 1, 2 or 3, the path to root is
reduced.
9
/ / \ \
4 5 6 3
/ / \ / \
0 7 8 1 2
两种技术相辅相成。每个操作的时间复杂度甚至比
O(logn)
〜O(n)
小。实际上,摊销的时间复杂度实际上变为小的常数。我没有发布具有上述优化的代码,因为这是我猜想的赋值部分。希望能帮助到你!