由网友(你會腻我何必)分享简介：我已经搜索周围的时间复杂一些帮助，而无法找到变量里面的for循环都是基于现有的循环变化多的时候。我写的功能，在code，并运行它试图进一步我的理解，但我只是没有能够抓住它，把它变成一个公式。也许如果有人能告诉我如何以可视化的配方一些提示，这将是真棒！如果没有在这里废话少说是我写了以下功能：i've searched...

我已经搜索周围的时间复杂一些帮助，而无法找到变量里面的for循环都是基于现有的循环变化多的时候。我写的功能，在code，并运行它试图进一步我的理解，但我只是没有能够抓住它，把它变成一个公式。也许如果有人能告诉我如何以可视化的配方一些提示，这将是真棒！如果没有在这里废话少说是我写了以下功能：

i've searched around for some help on time complexity, and wasn't able to find much when the variables inside the for loops are all changing based on the prior for loops. I wrote the function up in code, and ran it to try to further my understanding, however I'm just not able to grasp it and put it into a formula. Maybe if someone could show me some tips on how to visualize the formula, that would be awesome! Without further ado here is the function I wrote up:

    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 =（号），世界您好打印xtimes，N = 5，10，N = 6，20倍，N = 7，35X，每组8只，56X，N = 9，84X，N = 10，120倍

So i've ran the function based on different input sizes, and have gathered these results: if n = (number), Hello world is printed xtimes, n=5, 10x, n=6, 20x, n=7, 35x, n=8, 56x, n=9, 84x, n=10, 120x

我已经绘制它，理解它是一个函数，成长为以指数速度，但是我不知道在precise公式是什么这一点。我也看到，当n = 5，你好世界变得输出的patttern，N-2，N-3，N-4次，然后回到中间环，然后回到内心，运行N-3，正的4倍，回到中间，然后再返回到内运行正的4倍。

I've graphed it, and understand it is a function that grows as an exponential rate, however I'm not sure what the precise formula would be for this. I also see that when n=5, hello world gets output in a patttern of, n-2, n-3, n-4 times, then goes back to the middle loop, and then back to inner, running n-3, n-4 times, back to the middle, and then back to inner to run n-4 times.

如果有人可以帮助我想象这更好的，或点我在正确的方向，这将是真棒！我感觉好像我是非常接近的答案。感谢您的时间！

If someone could help me visualize this better, or point me in the right direction, that would be awesome! I feel as though I'm very close to the answer. Thanks for your time!

推荐答案

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

This is O(n^3), since the constants and lower-order terms are discarded for time complexities.

如果我们不放弃这些东西，它会是（N - 2）*（N - 1）/ 2 * N / 3。您可以推导出这个方程自己通过执行以下操作：

If we didn't discard those things, it'd be (n - 2) * (n - 1)/2 * n/3. You can derive this equation yourself by doing the following:

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 %dn", 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

For n = 1000, this prints "998 498501 166167000". To get from 998 to 498501 we multiply by 499.5, which is (n - 1)/2. To get from 498501 to 166167000, we multiply by 333.3333, which is n/3. And 998 is obviously (n - 2). Put it together and you get (n - 2) * (n - 1)/2 * n/3.

如果您简化它，你会得到这样的：

If you simplify it, you get this:

(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）。

But since we do remove constants and lower-order terms, that simplifies to O(n^3).