complexity-theory - 三个嵌套for循环的渐近分析

Question

我想计算这个嵌套 for 循环的 theta 复杂度：

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

我会说它是 n^3，但我认为这是不正确的，因为每个 for 循环都不会从 1 变为 n。我做了一些测试：

n = 5 -> 10

10 -> 120

30 -> 4060

50 -> 19600

所以它必须在n^2和n^3之间。我尝试了求和公式等，但我的结果太高了。虽然是 n^2 log(n)，但这也是错误的......

score 4 · Accepted Answer

4

使用 Sigma 表示法是一种高效的分步方法：

在此处输入图像描述

于 2014-05-01T16:52:20.403 回答

score 3 · Accepted Answer

3

它是O(N^3)。确切的公式是(N*(N+1)*(N+2))/6

于 2013-02-24T14:17:56.550 回答

2 回答 2