算法导论 4-2 - newdye的专栏 - 博客频道 - CSDN.NET

算法导论 4-2 - newdye的专栏 - 博客频道 - CSDN.NET

找出所缺的整数

某数组A[1..n]含有所有从0到n的整数，但其中有一个整数不再数组中。通过利用一个辅助数组B[0..n]来记录A中出现的整数，很容易在O(n)时间内找出所缺的整数。但是在这个问题中，我们却不能由一个单一的操作来访问A中的一个完整整数，因为A中的元素是以二进制表示的。我们所能用的唯一操作就是"取A[i]的第j位"，这个操作所花的时间为常数。

证明：如果仅用此操作，仍能在O(n)时间内找出所缺的整数。

2 分析与解答

显然要运用递归思想，如果n为基数，那么0~n有(n+1)/2个奇数和(n+1)/2个偶数；同理当n为偶数时，有n/2+1个偶数，和n/2个奇数。

所以，假设如果A[1..n]中偶数个数不足，那么就要在A[1..n]的偶数元素中查找所缺整数，那么每次查找的数量就减半；将偶数元素左移一位得到的数组同样具有上述特性。反复应用此方法，直到两种情况：

1. 奇数个数为0说明缺的位为1；
2. 只剩一位时，不存在的那位就是所缺的；

这样就能得到基本递归算法，可以得到递归式T(n)=T(n/2)+D(n)+C(n)；

在来看D(n)显然分解需要扫描整个A[1..n]，所以D(n)=O(n)；

对于C(n)，算法应该不需合并，推测其时间复杂度为常数，即C(n)=O(1)；

所以，若算法满足上述条件，递归式为T(n)为T(n)=T(n/2)+O(n)，根据主定理可得，此递归式解为T(n)=O(n)。

证明：可以找到满足上述条件的算法。

设取A[i]的第j位操作为value(A[i],j)；

因为整数在A中以二进制形式存储，那么value(A[i], 0)就代表A中元素的奇偶性；

而value(A[i], 1)就代表A中元素左移一位的奇偶性，以此类推，直至奇数个数为0或只剩1位。

Read full article from 算法导论 4-2 - newdye的专栏 - 博客频道 - CSDN.NET