将嵌套 for 循环转换为低于 O(n^3)

Question

所以，我有这段代码，我需要以小于 O(n^3) 的时间复杂度使其成为运行。我刚刚开始学习复杂性，我真的不知道该怎么做。

int n, i, j, k, x=0;
printf("Type n: \n");
scanf("%d",&n);


for(i=1; i<n; i++)
{
    for(j=1; j<i; j++)
    {
        for(k=1; k<j; k++)
        {
            x=x+1;
        }
    }
}
printf("%d\n",x);

我想我明白为什么它是 O(n^3)，但我真的不知道如何让它更有效率。我试着把它变成一个递归函数，可以吗？

Answer 1

您要为每个 i、j、k 的结果加 1，且 0 < k < j < i < n。有 choose(n-1, 3) 这样的 i, j, k 值（{1, 2, ..., n-1} 的每个大小为 3 的子集一个）。（此处二项式系数函数中"choose"）

因此，您可以用 choose(n-1, 3) 替换基于循环的计算，如果 n 为正，则为 (n - 1)(n - 2)(n - 3) / 6。

int n;
printf("Type n: \n");
scanf("%d",&n);
printf("%d\n", n > 0 ? (n-1)*(n-2)*(n-3)/6 : 0);

这是 O(1) 计算结果，O(log N) 输出它（因为结果有 O(log N) 位）。

Answer 2

您当前的函数只是一种糟糕的 O(n^3) 计算某些数学函数的方法...

x 将最终等于迭代次数。

您的作业可能会将 for 循环重新解释为方程式。

我们知道外循环将执行它的块 (n-1) 次。下一个内部循环将总共执行其块 1+2+..+(n-2) 次。 That's (n-1)(n-2)/2 次。 (此时我自己卡住了，none 我的外推得到 (n-1)(n-2)(n-3)/6)

另一种方式：因为我们知道 1, 2, 3 都是零根，所以我们也知道 least 处的函数是 (n - 1)(n - 2)(n - 3)。求解 n=4 得到 1/6 作为常数因子。

Answer 3

我重构了你的循环如下：

for(i=1; i<n-2; i++)
{
    x = x + ( ( i * ( i + 1 ) ) / 2 );
}

这是有效的，因为 ( ( i * ( i + 1 ) ) / 2 ) = 系列 1 到 i 中所有值的总和。

你最内层的循环（使用变量 k）相当于将 j 的值加到 x。你的第二个循环（使用变量 j）相当于计算系列 1 到 i 的总和。

所以我用系列 1 到 i 的总和替换了你的第二个和第三个循环。我们保留您的第一个循环，并在每次迭代时将系列 1 到 i 的总和添加到您之前的值。

请注意，我在您的外循环中添加了一个 -2 以模拟您的两个内循环中的 < 符号。如果您的要求是 <= 在每个内部循环上，则不需要 -2。

这是一个 O(n) 的解决方案，不如。

将嵌套 for 循环转换为低于 O(n^3)

Converting nested for loop into lower than O(n^3)

c

big-o

time-complexity