gpt4 book ai didi

algorithm - Quick Union 的时间复杂度是多少?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:47:38 26 4
gpt4 key购买 nike

我正在学习关于数据结构和算法的 coursera 类(class)。作者提到 Quick Find 是 O(N^2),这是有道理的(假设 N 个对象上的 N 个联合操作可能需要 N*N 个数组访问)。但是,我不明白为什么 Quick Union 会更好。似乎在最坏的情况下,一棵又长又窄的树,对 N 个对象的 N 个 Find 操作也会导致 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() 时将树展平。当为元素 x 调用 find() 时,返回树的根。 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)还要小。事实上,摊销时间复杂度实际上变成了小常量。

我没有发布经过上述优化的代码,因为我猜这是赋值部分。希望对您有所帮助!

关于algorithm - Quick Union 的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43036204/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com