在算法 4 的 1.4.5.3 节中,对 2-sum 有这样的一段说明:
是否存在解决 2-sum 问题的线性级别的算法,3-sum 问题的线性对数级别的算法?对于 2-sum ,这个问题的回答是没有(成本模型仅允许使用并计算这些整数的线性或是平方级别的函数中的比较操作)...
Is there a linear algorithm for 2-sum or a linearithmic algorithm for 3-sum? The answer to this question is no for 2-sum (under a model that counts and allows only comparisons of linear or quadratic functions of the numbers)...
简单来说,我不懂 2-sum 的下界是如何确定的。2-sum 的成本模型是访问数组的次数,文中是如何由 2-sum 的成本模型确定了 2-sum 的下界?
任何提示或想法都可能有帮助。谢谢。