-3

在 coursera 课程中，以下联合查找仅适用于数字： 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 多年的计算机时间！
4

1 回答 1

1

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

如果你有 10 亿个整数的内存，你需要大约 1 秒来查看它们，因此对这 40 亿个整数执行 O(n) 的算法将需要 1 秒。如果算法为 O(n 2 )，则需要 10 18次操作，即 10 亿秒，大约等于 31 年。

于 2016-10-10T02:20:49.543 回答