算法(4th ed)(168):基础——算法分析 6.5.2

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

算法(4th ed)(168):基础——算法分析 6.5.2

(设计更快的算法:3-sum 问题的快速算法)

这种方式对 3-sum 问题同样有效。和刚才一样,我们假设所有整数均各不相同。当且仅当 -(a[i] + a[j]) 在数组中(不是 a[i] 也不是 a[j])时,整数对 (a[i]a[j]) 为某个和为 0 的三元组的一部分。下面代码框中的代码会将数组排序并进行 N(N1)/2 次二分查找,每次查找所需的时间都和 logN 成正比。因此总运行时间和 N2logN 成正比。可以注意到,在这种情况下排序的成本是次要因素。这个解法也使我们能够解决更大规模的问题(请见练习 1.4.42)。图 1.4.6 显示了用这 4 种算法解决我们提到过的几种问题规模时的成本的悬殊差距。这样的差距显然是我们追求更快的算法的动力。

算法(4th ed)(168):基础——算法分析 6.5.2

图 1.4.6 解决 2-sum 和 3-sum 问题的各种算法的成本

评论

发布