Union find：快速查找，作者是如何得出这些数字的（缩放）

Question

在 coursera 课程中，下面的 union find 仅针对数字实现： https://www.coursera.org/learn/introduction-to-algorithms/lecture/EcF3P/quick-find

public class QuickFindUF
{
 private int[] id;
 public QuickFindUF(int N)
 {
 id = new int[N];
 for (int i = 0; i < N; i++)
 id[i] = i;
 }
 public boolean connected(int p, int q)
 { return id[p] == id[q]; }
 public void union(int p, int q)
 {
 int pid = id[p];
 int qid = id[q];
 for (int i = 0; i < id.length; i++)
 if (id[i] == pid) id[i] = qid;
 }
}

幻灯片最后，每秒10^9次运算和其他10^x个数（包括10）是如何计算的？所有数字都在下图中：（下面也复制了文字）

粗略标准（目前）。

• 每秒 10^9 次操作。
• 主存10^9个字。
• 在大约 1 秒内触摸所有字词。

例如。快速查找的大问题。

• 10^9 个对象上的 10^9 个联合命令。
• 快速查找需要超过 10^18 次操作。
• 30 多年的计算机时间！

Answer 1

这些数字是计算机处理速度 (GHz) 和内存大小（G "Words"，即整数或 4GB）的数量级估计值。

如果你有 10 亿个整数的内存，你将花费大约 1 秒的时间来查看它们，因此对这 40 亿个整数的 O(n) 算法将花费 1 秒。如果算法是O(n²)则需要10¹⁸次操作，即10亿秒，约等于31年。