算法(4th ed)(167):基础——算法分析 6.5.1

阅读数:30 2019 年 11 月 6 日 07:59

算法(4th ed)(167):基础——算法分析 6.5.1

(设计更快的算法:热身运动 2-sum)

我们先来考虑这个问题的简化版本,即找出一个输入文件中所有和为 0 的整数对的数量。简单起见,我们还假设所有整数均各不相同。这个问题很容易在平方级别解决,只需将ThreeSum.count() 中关于 k 的循环和 a[k] 去掉即可得到一个双层循环来检查所有的整数对,如表 1.4.7 中的平方级别条目所示(我们将这个实现称为 TwoSum)。下面这个实现显示了归并排序和二分查找是如何在线性对数级别解决 2-sum 问题的。改进后的算法的思想是当且仅当 -a[i] 存在于数组中(且 a[i] 非零)时,a[i] 存在于某个和为 0 的整数对之中。要解决这个问题,我们首先将数组排序(为二分查找做准备),然后对于数组中的每个 a[i],使用 BinarySearch 的rank() 方法对-a[i] 进行二分查找。如果结果为 jj>i,我们就将计数器加 1。这个简单的条件测试覆盖了三种情况:

  • 如果二分查找不成功则会返回 -1,因此我们不会增加计数器的值;
  • 如果二分查找返回的 j>i,我们就有 a[i] + a[j] = 0,增加计数器的值;
  • 如果二分查找返回的j0i 之间,我们也有 a[i] + a[j] = 0,但不能增加计数器的值,以避免重复计数。

这样得到的结果和平方级别的算法得到的结果完全相同,但它所需的时间要少得多。归并排序所需的时间和 NlogN 成正比,二分查找所需的时间和 logN 成正比,因此整个算法的运行时间和 NlogN 成正比。像这样设计一个更快的算法并不仅仅是一种学院派的练习——更快的算法使我们能够解决更庞大的问题。例如,你现在可以在可接受的时间范围内在计算机上解决 100 万个整数(1Mints.txt)的 2-sum 问题了,但如果用平方级别的算法你肯定需要等上很长很长的时间(请见练习 1.4.41)。

算法(4th ed)(167):基础——算法分析 6.5.1

2-sum 问题的线性对数级别的解法

评论

发布