3-sum 替代方法

Question

我尝试了 3sum problem 的另一种方法：给定一个数组，查找总和为给定数字的所有三元组。

基本上方法是这样的：对数组进行排序。一旦选择了一对元素（比如 A[i] 和 A[j]），就会对第三个元素进行二进制搜索 [使用 equal_range function]。最后一个匹配元素的索引保存在变量 'c' 中。由于 A[j+1] > A[j]，我们只搜索并排除索引 c（因为索引 c 及以后的数字总和肯定会大于目标总和）。对于 j=i+1 的情况，我们将结束索引保存为 'd' 并使 c=d。对于 i 的下一个值，当 j=i+1 时，我们只需要搜索并排除索引 d。

C++ 实现：

int sum3(vector<int>& A,int sum)
{
    int count=0, n=A.size();
    sort(A.begin(),A.end());
    int c=n, d=n;  //initialize c and d to array length
    pair < vector<int>::iterator, vector<int>::iterator > p;
    for (int i=0; i<n-2; i++)
    {
        for (int j=i+1; j<n-1; j++)
        {
            if(j == i+1)
            {
                p=equal_range (A.begin()+j+1, A.begin()+d, sum-A[i]-A[j]);
                d = p.second - A.begin();
                if(d==n+1) d--;
                c=d;
            }
            else
            {
                p=equal_range (A.begin()+j+1, A.begin()+c, sum-A[i]-A[j]);
                c = p.second - A.begin();
                if(c==n+1) c--;
            }
            count += p.second-p.first;
            for (auto it=p.first; it != p.second; ++it) 
                cout<<A[i]<<' '<<A[j]<<' '<<*it<<'\n';
        }
    }
    return count;
}

int main()      //driver function for testing
{
    vector <int> A = {4,3,2,6,4,3,2,6,4,5,7,3,4,6,2,3,4,5};
    int sum = 17;
    cout << sum3(A,sum) << endl;
    return 0;
}

我无法计算出此算法所需的上限时间。我知道最坏的情况是目标金额大得无法实现。

我的计算结果如下：

对于 i=0，没有。二分查找的次数是 lg(n-2) + lg(n-3) + ... +lg(1)

对于 i=1，lg(n-3) + lg(n-4) + ... + lg(1)

...

对于 i=n-3，lg(1)

总的来说，lg((n-2)!) + lg((n-3)!) + ... + lg(1!) = lg(1^n*2^(n-1)3^(n-2)...*(n-1)^2*n^1)

但是如何从这个表达式中推导出 O(n) 的界限呢？

Answer 1

计算复杂度时，我先参考Big-O Cheat sheet。我使用此 sheet 对较小的代码部分进行分类以获得它们的运行时性能。

例如如果我有一个简单的循环，它将是 O(n)。 BinSearch（根据秘籍sheet）是O(log(n))，等等

接下来，我使用 Properties of Big-O notation 将较小的部分合成在一起。

例如，如果我有两个相互独立的循环，它将是 O(n) + O(n) 或 O(2n) => O(n)。如果我的一个循环在另一个循环中，我会将它们相乘。所以 g( f(x) ) 变成 O(n^2).

现在，我知道你在说："hey, wait, I'm changing the upper and lower bounds of the inner loop" 但我认为这并不重要...here's a university level example.

所以我对你的运行时间的粗略计算是 O(n^2) * O(Log(n)) 或 O(n^2 Log(n))。

但事实并非如此。我可能会做一些非常错误的事情。所以我的下一步是开始绘制最坏情况下的运行时间图。将 sum 设置为不可能的大值并生成越来越大的数组。您可以通过使用大量重复的较小数字来避免整数溢出。

此外，将其与 Quadratic 3Sum Solution 进行比较。这是一个已知的 O(n^2) 解决方案。一定要比较最坏的情况，或者至少比较两个相同的数组。同时进行两个定时测试，这样您就可以在根据经验测试运行时时开始感受哪个更快。

发布版本，针对速度进行了优化。

Answer 2

除了 James 的好回答之外，我想指出的是，在最坏的情况下，这实际上可以上升到 O (n^3)，因为你是运行 3 个嵌套的 for 循环。考虑案例

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

求和是3。

Answer 3

1. 对于您的分析，请注意 log(1) + log(2) + ... + log(k) = Theta(k log(k))。实际上，这个总和的上半部分是 log(k/2) + log(k/2+1) + ... + log(k)，所以它至少是 log(k/2)*k/2，它已经渐近地与 log(k)*k 相同。同样，我们可以得出结论

log(n-1) + log(n-2) + log(n-3) + ... + log(1) +  // Theta((n-1) log(n-1))
           log(n-2) + log(n-3) + ... + log(1) +  // Theta((n-2) log(n-2))
                      log(n-3) + ... + log(1) +  // Theta((n-3) log(n-3))
                                 ... +
                                       log(1) = Theta(n^2 log(n))

事实上，如果我们考虑至少为 log(n/2) 的对数，它就是左上象限的半三角形（因此 ~1/2）（因此 ~n^2/4 ) 上面的总和，所以有 Theta(n^2/8) 这样的项。

2. 正如 satvik 在另一个答案中指出的那样，当输出数量本身为 Theta(n^ 3),也就是他们都相等的时候。

3. 3-sum 问题有 O(n^2) 个解，因此渐近速度比这个快。

3-sum 替代方法

3-sum alternative approach

c++

algorithm

array-algorithms