algorithm - 具有可变时间复杂度的嵌套 for 循环

Question

我四处寻找有关时间复杂度的帮助，但当 for 循环内的变量都基于先前的 for 循环发生变化时，我找不到太多帮助。我用代码编写了该函数，并运行它以尝试加深我的理解，但是我就是无法掌握它并将其放入公式中。也许如果有人可以告诉我一些关于如何可视化公式的提示，那就太棒了!事不宜迟，这里是我写的功能:

    public static void function2(){
Scanner scanner = new Scanner(System.in);
System.out.println("enter a value for n: ");
int n = scanner.nextInt();
int counter = 0;
for (int i = 1; i <= (n-2); i++){
    System.out.println("Entered outer loop");
    for (int j = i+1; j<= (n-1); j++){
        System.out.println("Entered middle loop");
        for (int k = j+1; k<= n; k++){
            System.out.println("Entered inner loop");
            System.out.println("Hello World");
            counter++;
        }
    }
}
 System.out.println("Hello world printed: " + counter + " times");
}

所以我根据不同的输入大小运行了该函数，并收集了这些结果: 如果n = (number)，Hello world打印x次，n=5, 10x, n=6, 20x, n=7, 35x, n=8, 56x, n=9, 84x, n=10, 120x

我已将其绘制成图表，并了解它是一个以指数速率增长的函数，但我不确定具体的公式是什么。我还看到当 n=5 时，hello world 以 n-2、n-3、n-4 次的模式输出，然后返回到中间循环，然后返回到内部，运行 n-3， n-4次，回到中间，再回到内部跑n-4次。

如果有人可以帮助我更好地想象这一点，或者为我指明正确的方向，那就太棒了!我觉得我离答案很近了。感谢您的宝贵时间!

Answer 1

这是 O(n^3)，因为常量和低阶项因时间复杂度而被丢弃。

如果我们不丢弃这些东西，它将是 (n - 2) * (n - 1)/2 * n/3。您可以通过执行以下操作自行推导此等式:

int n = 1000;
int loop1 = 0, loop2 = 0, loop3 = 0;
for (int i = 1; i <= (n-2); i++){
    loop1++;
    for (int j = i+1; j<= (n-1); j++){
        loop2++;
        for (int k = j+1; k<= n; k++){
            loop3++;
        }
    }
}
printf("%d %d %d\n", loop1, loop2, loop3);

对于 n = 1000，这将打印“998 498501 166167000”。为了从 998 到 498501，我们乘以 499.5，即 (n - 1)/2。为了从 498501 到 166167000，我们乘以 333.3333，即 n/3。而 998 显然是 (n - 2)。把它放在一起，你会得到 (n - 2) * (n - 1)/2 * n/3。

如果你简化它，你会得到这个:

(n - 2) * (n - 1)/2 * n/3
(n - 2) * (n/2 - 1/2) * n/3
(n - 2) * (n/2 * n/3 - 1/2 * n/3)
(n - 2) * ((n^2)/6 - n/6)
(n^2)/6 * (n - 2) - n/6 * (n - 2)
n * (n^2)/6 - 2 * (n^2)/6 + n * -n/6 - 2 * -n/6
(n^3)/6 - (n^2)/3 - (n^2)/6 + n/3

(n^3)/6 - (n^2)/2 + n/3

但由于我们确实删除了常量和低阶项，因此简化为 O(n^3)。