java - 如何找到以下代码的最坏情况复杂度？

Question

需要了解以下代码的最坏情况下的复杂度，如能提供解决步骤，将不胜感激。我在想答案 n^3logn，但不确定。

int complexity(int n)
  int i,j,c
  for(i=1; i < n; i=i*3)
    for(j=n; j < n*n; j++)
      c++
  for(i=c; i > 0; i--)
    if(random(0...999) > 0)
      for(j=0; j < 3*n; j++)
        c++
    else
      for(j=2*n*n; j > 0; j--)
        c++
  return c

Answer 1

让我们看看第一个嵌套循环

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

外层循环运行 log(n) 次 [log base 3，但基数变化乘以一个不影响渐近复杂度的常数] 和内层循环 n^2 次，因此在此循环之后 c = n^2 * log(n)。

对于第二个循环:

for(i=c; i > 0; i--)
    if(random(0...999) > 0)
       for(j=0; j < 3*n; j++)
          c++
   else
      for(j=2*n*n; j > 0; j--)
        c++

在最坏的情况下，else 情况总是会发生，因此我们可以将其修改为

for(i=c; i > 0; i--)
  for(j=2*n*n; j > 0; j--)
    c++

外循环发生 c 次，即 O(n^2 * log(n)) 内循环递增 c 2*n^2，所以 c 增加 2 * n^2 * n^2 * log(n)，添加我们得到 c 的初始值(因此整体复杂度)在 O(2*n^4*log(n) + n^2 * log(n)) = O( n^4 * log(n))