c 中的时间复杂度（嵌套循环）

Question

我很难弄清楚这两个代码的时间复杂度。

c = 0;
for (i = 0; i < n*n; i++) 
for (j = 0; j < i; j++) 
 c = c + 1;

上面代码中外层循环的时间复杂度是n^2，在内层循环中很难找到。

j = 1; c = 0;
for(i = 1; i <= n; i = i + 1) { 
 for(k = 1; k <= j; k = k + 1) { 
 c = c + 1; 
 } 
j = j * 2; 
}

在第二个代码中我认为外循环的时间复杂度是n，内循环是2^n。我认为这两个 ((n)*2^n) 的倍数是整个时间复杂度。这样对吗？感谢阅读

Answer 1

第一个有 O(n^4)，因为 (n*n)^2。第二个有 O(n * 2n)=O(n^2).

Answer 2

在第一个代码中，您从 1 迭代到 n^2。这意味着您的迭代次数是 0、1、2、3，.......n*n - 1。AP 中的这个系列。

 Sum of series in AP = N(N+1)/2 = n^2(n^2+1)/2
 Time Complexity is O(n^4)

在第二个代码中，您从 1 迭代到 n。因此，内部循环将相应地迭代 1、2、4、...2^n。这个系列在 GP

 Sum of series in GP = a(r^n-1)/r-1 = 2^n
 Time complexity is O(2^n)

Time complexity in c (nested loop)