《编程珠玑》43亿整数找重复数 Jim Saxe线性算法原理疑问

书籍原文摘录 #

问题：给定一个包含4,300,000,000个整数的文件，如何找到其中至少出现两次的整数？

解法：二分查找思路通过递归搜索包含超过半数整数的子区间，定位至少出现两次的元素。作者最初的方案无法保证每次迭代处理的整数数量减半，因此log₂n次遍历的最坏情况运行时间与n·log n成正比。Jim Saxe将其优化为线性时间，核心观察是搜索过程无需保留过多重复值：当搜索确定重复值必然存在于大小为m的整数区间内时，当前工作磁带上仅存储m+1个整数；若待写入磁带的整数超过该数量，程序直接丢弃多余值。该方法虽然会频繁忽略输入值，但策略足够保守，可保证找到至少一个重复值。

对原始二分方案的理解 #

我理解的原始递归分区统计流程步骤如下：

• 检测每个32 bit整数的第一位，若为0则存入第一个文件，若为1则存入另一个文件
• 整数数量超过n/2的文件必然存在重复数，取该文件的数进入下一轮检测
• 检测每个32 bit整数的第二位，生成大小为原分区1/4的分区文件
• 递归执行该过程min(32, logn)次，若最终分区包含超过1个数，该分区即为存在重复的分区

原方案最坏场景为所有n个数完全相同，此时每轮都需要检测n个数，总操作量为n × logn，时间复杂度为O(nlogn)，每轮处理量序列如下：

n
n
n
...

疑问点 #

我无法理解Jim Saxe的方法为何能将复杂度降至线性：按照书中描述，Jim Saxe的方案对每个分区仅保留比分区应容纳数量多1的数。例如若所有n个数最高位都为0，原方案会将所有n个数放入对应分区，而Jim的方案仅保留n/2 + 1个数，按这个逻辑每轮待检测的数都会减半，处理量序列为：

n
n/2 + 1
n/4 + 1
...

按此计算总操作量为(n × logn) / 2，时间复杂度仍为O(nlogn)，并没有达到线性，我的理解哪里出现了偏差？

解答 #

你的核心错误是算错了总操作量的求和结果，Jim Saxe方案的处理量是公比为1/2的收敛等比数列，总和为常数倍n，属于严格线性时间：

• 你列出的单轮处理量序列是正确的：第一轮扫描全量n个原始输入，第二轮处理上一轮留存的n/2 +1个元素，第三轮处理n/4 +1个元素，因为是32位定长整数，整个递归最多跑32轮就会定位到具体重复值。
• 对序列求和的正确结果如下：

  总操作量 = n + (n/2 + 1) + (n/4 + 1) + ... + (n/2^31 + 1)
          = n * (1 + 1/2 + 1/4 + ... + 1/2^31) + 32
          < 2n + 32
  

  公比小于1的等比数列和是收敛的：1 + 1/2 +1/4 + ...的无穷项和极限为2，哪怕算上32轮每轮额外多存的1个元素，总操作量也不会超过2n + 32，根本不存在logn的乘数因子。
• 你之前算出(n*logn)/2是错误套用了等差数列的求和逻辑，误以为处理量随轮次线性叠加和n相乘，实际上每轮处理量是折半衰减的，轮次再增加总和也不会超过首项的2倍，额外加的32次常数操作在大O表示法中可以直接忽略。
• Jim的方案全程仅需要在第一轮读取一次全量原始输入，后续所有轮次处理的都是上一轮留存的少量元素，不需要回溯重读原始文件，这是它和原始O(nlogn)方案的核心差异。

内容的提问来源于stack exchange，提问作者hello.wjx