algorithm - 编程珍珠 : Finding the missing integer in a file of 4 billion integers

Question

问题:输入在顺序文件中。该文件最多包含 40 亿个整数。查找缺失的整数。

解决方案据我理解:

1. 制作两个临时文件，一个以0开头，一个以1开头

2. 两个MUST之一(4.3B鸽子洞和4B鸽子)小于2B。选择文件并在第 2 位重复步骤 1 和 2，然后在第 3 位等等。

本次迭代的结束条件是什么？

此外，书中提到算法的效率为 O(n)但是，

第 1 次迭代 => n 个探测操作
第二次迭代 => n/2 次探测操作
.
.
.
n + n/2 + n/4 +... 1 => nlogn??

我错过了什么吗？

Answer 1

您将检查这两个文件并选择元素最少的文件。

您将重复该过程，直到您完成所有 32 位，最后您将拥有一个文件 0 元素。这是其中一个丢失的数字应该在的地方。因此，如果您一直在跟踪到目前为止过滤的位，您就会知道数字应该是多少。

请注意，这是查找一个(即“任何”)缺失的数字。如果给定一个包含 40 亿(不是 2^32 (4294967296))个整数的(无序)序列列表，您必须找到一个缺失的整数，这将不起作用，因为您可以在一开始就切断缺失的整数。

还有:

n + n/2 + n/4 + ... 1 <= 2n

不是n log n .

这是一个geometric sequence与 a = n, r = 1/2 ，可以用以下公式计算:

n (1-(1/2)^m)
-------------
  1 - (1/2)

自 0 < (1/2)^m < 1对于任何正数 m (因为 0 < 1/2 < 1 )，我们可以说 (1-r^m) < 1因此我们可以说最大值是:

  n.1
-------
1 - 1/2

   n
= ---
  1/2

= 2n