n个数字中可能的三角形总数

考虑两对(i,j1)和(i,j2)j1 <= j2.很容易看出k2(在步骤2中找到(i,j2))> = k1(找到(i,j1)的一步).这意味着如果你迭代j,你只需要检查从前一个k开始的数字.因此,它为每个特定的i 提供O(n)时间复杂度,这意味着整个算法的O(n ^ 2).

C++源代码:

int Solve(int* a, int n)
{
    int answer = 0;
    std::sort(a, a + n);

    for (int i = 0; i < n; ++i)
    {
        int k = i;

        for (int j = i; j < n; ++j)
        {
            while (n > k && a[i] + a[j] > a[k])
                ++k;

            answer += k - j;
        }
    }

    return answer;
}

downvoters的更新:

这肯定是O(n ^ 2)!请仔细阅读Thomas H. Cormen关于摊销分析(第二版中的17.2)的章节"算法介绍". 通过计算嵌套循环来发现复杂性有时是完全错误的. 在这里,我试着尽可能简单地解释它.让我们修复i变量.然后为我我们必须遍历Ĵ从我到Ñ(这意味着为O(n)的操作)和内部while循环迭代ķ从我到Ñ(这也意味着为O(n)操作).注意:我不会从每个j的开头循环开始.我们还需要为每个从0到n的 i做.所以它给出了 n*(O(n)+ O(n))= O(n ^ 2).