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

Question

如果n给出数字,我如何找到可能的三角形总数？有没有什么方法能在不到一定的O(n^3)时间内完成这项工作？

我正在考虑a+b>c,b+c>a以及a+c>b成为三角形的条件.

Answer 1

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

1. 1 1 1
2. 1 2 2
3. 1 3 3
4. 2 2 2
5. 2 2 3
6. 2 3 3
7. 3 3 3

如果这些假设中的任何一个不成立,则很容易修改算法.

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

1. 排序数字(升序).我们将取三元组ai <= aj <= ak,使得i <= j <= k.
2. 对于每个i,j,您需要找到满足ak <= ai + aj的最大k.然后,所有的三元组(AI,AJ,人).J <= 1 <= k是三角形(因为AK> = AJ> =人工智能我们只能违反AK <A I + AJ).

考虑两对(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).

Answer 2

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

• 假设您希望所有三角形都作为三元组(a, b, c)，其中a <= b <= c。
• 有 3 个三角形不等式，但仅此而已a + b > c（其他不等式则微不足道）。

现在：

• 对 中的序列进行排序O(n * logn)，例如通过合并排序。
• 对于每一对(a, b), a <= b，剩余值c必须至少b小于a + b。
• 所以你需要计算区间内的项目数[b, a+b)。

这可以简单地通过对 a+b ( O(logn))进行二分搜索并计算[b,a+b)ba 的每种可能性的项目数来完成。

所有在一起O(n * logn + n^2 * logn)是O(n^2 * logn)。希望这可以帮助。