gpt4 book ai didi

java - 为什么在 Weighted QuickUnion 中联合和查找操作期间的数组访问次数据说是 lg(N) 的顺序?

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

快速联合算法的通用代码。

public class QuickUnionUF
{
private int[] id;
public QuickUnionUF(int N)
{
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
}
private int root(int i)
{
while (i != id[i]) i = id[i];
return i;
}
public boolean connected(int p, int q)
{
return root(p) == root(q);
}
public void union(int p, int q)
{
int i = root(p);
int j = root(q);
id[i] = j;
}
}

enter image description here

这里很明显,对于像“初始化”、“联合”和“查找是否连接”这样的联合操作,数组访问的次数将是 N 的数量级(从代码中可以很清楚地看出)。

然而,我的书声称,如果我们将 QuickUnion 修改为 Weighted QuickUnion,那么数组访问的数量将变为 lg(N) 的数量级。但我无法从代码中看出如何。

Weighted QuickUnion 所做的唯一更改是 union() 函数中的部分,如下所示:

 int i = root(p);
int j = root(q);
if (i == j) return;
if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
else { id[j] = i; sz[i] += sz[j]; }

这里我们维护额外的数组sz[i]计算以 i 为根的树中对象的数量。

但是在这里,我看不到 union 的数组访问次数是 lg(N) 阶的。数组访问必须是 N 阶,因为我们必须调用 root() 方法两次。另外 lg(N) 的顺序如何,即使对于“查找是否连接”操作也是如此?

我对他们如何获得 lg(N) 感到困惑。有人可以解释一下吗?

最佳答案

在未修改的版本中,您获得线性依赖性,因为到父级的链接可以是任意的。因此,在最坏的情况下,您最终可能会得到一个长列表(即,如果您位于列表的末尾,则必须遍历所有其他元素)。

修改(按等级合并)旨在通过使较小的子树成为较大子树的根的子树来生成较浅的树。这种启发式方法使树更加平衡,即从任何叶子到其根的路径长度变为 O(log n)。请记住,具有 k 个节点的完整二叉树的高度是 O(log k)

更正式的证明,请引用现有文献。

附加说明:我提到过按等级联合只是一种启发式方法。理想情况下,您会希望根据两个子树的高度做出决定。但是,跟踪高度非常困难。这就是为什么您通常使用子树的大小,它与其高度相关。

关于java - 为什么在 Weighted QuickUnion 中联合和查找操作期间的数组访问次数据说是 lg(N) 的顺序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45770295/

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