什么是嵌套循环的 Big-O，其中外层循环是 n^2

Question

for(int i = 1; i < n **2; i++) 
{    
   for(int j = 1; j < i; j++)    
   {
     s = s;    
   } 
}

既然外层循环的大 O 是 O(n^2)，它仍然会乘以内层循环使得总的大 O 符号为 n(n^2) -> O(n^3) ？

Answer 1

在外循环中，我可以取值从 1 到 n^2。然后对于这些值中的每一个，内部循环从 1 到 i。 i=1执行的操作数是1，i=2是2，...，i = n^2是n^2。

所以总的操作次数是i从1到n^2的总和。这是一个众所周知的 series ，它具有 (n^2)(n^2 + 1)/2 的封闭形式，即 O(n^4)

What is the Big-O of a nested loop, where the outer loop is n^2