java - 两个内部嵌套循环运行时间

Question

void smiley (int n) { 

 for (int i = 0; i < n * n; ++i) { 
    for (int k = 0; k < i; ++k) 
      System.out.println(”k = ” + k); 
    for (int j = n; j > 0; j--) 
      System.out.println(”j = ” + j); 
   } 
} 

如您所见，有两个内部循环和一个外部循环。运行时间是 n^4。我得到 n * n使其成为 n^2，但是两个内部循环如何使总运行时间为 n^4？

聚苯乙烯

一种类似的情况，它的运行时间是 n^2。我也不明白。它有三个循环吧？

void smiley (int n, int sum) { 
 for (int i = 0; i < n * 100; ++i) { 
    for (int j = n; j > 0; j--) 
       sum++; 
    for (int k = 0; k < i; ++k) 
       sum++; 
    } 
} 

Answer 1

运行时间不是循环构造次数的函数，而是代码循环次数的函数。因此，如果一个循环执行了100次，并且包含一个执行了100次的内部循环，则该内部循环将执行10,000次。

对于第一种情况，外部循环为O(n ^ 2)，第一个内部循环为O(n ^ 2 * n ^ 2)，第二个内部循环为O(n ^ 2 * n)，因此总阶数是O(n ^ 2 + n ^ 4 + n ^ 3)，简化为O(n ^ 4)。

对于第二种情况，外部循环为O(n)，第一内部循环为O(n * n)，第二内部循环为O(n * n)，因此总阶为O(n + n ^ 2) + n ^ 2)，简化为O(n ^ 2)。