问N个数中可能的三角形总数

EN

假设在给定的n中没有相等的数字，并且允许多次使用一个数字。例如，我们给出了一个数字{1,2,3}，因此我们可以创建7个三角形：

1. 1 1 1
2. 1 2 2
3. 1 3 3
4. 2 2 2

H192 2 3

1. 2 3 3

H1133 3 3G215

如果这些假设中的任何一个都不是真的，那么很容易修改算法。

这里我给出的算法在最坏的情况下需要O(n^2)时间：

1. 排序编号(升序)。我们将取三个，使得i，<=，j，<=，k，

，

1. ，<=，

，

1. ，对于每个i，j，你需要找到最大的k，满足ak，<=，ai + aj。那么所有的三元组( ai，aj，al) j <= l <= k是三角形的(因为ak >= aj >= ai我们只能违反ak

考虑两对(i，j1)和(i，j2) j1 <= j2。很容易看到k2 (针对(i，j2)在步骤2中找到) >= k1 (针对(i，j1)在步骤2中找到)。这意味着如果你迭代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;
}

面向下一代投票者的更新：

这绝对是O(n^2)！请仔细阅读托马斯·H·科尔曼关于摊销分析的“算法简介”一章(第二版17.2)。通过计算嵌套循环来发现复杂性有时是完全错误的，在这里，我会尽可能简单地解释它。让我们修复i变量。然后，对于i，我们必须将j从i迭代到n(这意味着O(n)操作)，而内部循环将k从i迭代到n(这也意味着O(n)操作)。注意:对于每个 j，我不会从头开始执行while循环。我们也需要对每个i from to n做这个，所以我们得到n * (O(n) + O(n)) = O(n^2)。

在O(n^2*logn)中有一个简单的算法。

假设你想要所有的三角形都是三角形，其中a <= b <= c.

• There是3个三角形不等式，但只有a + b > c就足够了(其他的就很简单了)。

现在：

对间隔中的序列进行排序，例如，通过对每对进行排序，剩余的值必须至少为merge-sort.

• For且小于a + b.

• So。要计算O(n * logn) (a, b), a <= b中的项目数，c需要至少为b

这可以简单地通过二进制搜索a+b (O(logn))和计数每个可能性的[b,a+b)中的项目的数量是b-a。

所有的O(n * logn + n^2 * logn)，也就是O(n^2 * logn)。希望这能有所帮助。

如果你使用二进制排序，那是O(n-log(n))，对吗？将你的二叉树放在手边，并且对于每一对(a，b)，其中a，b和c< (a+b)。