c - 代码中的时间复杂度？

Question

我有 fun1 电话foo1()，需要O(n^6 + m^4). 你觉得时间复杂度是fun1多少？我的猜测是它会是O(2n^6 + m^4)！

int fun1(int n, int G[MAX][MAX])
{
  int x, ans;
  if(n < 2)
     return 1;
  for(x = 0; x < n; x++){
    G[n][x] = G[x][n] = 1;
  }
  ans = foo1(n+1, G);
  return ans;
}

fun2 还调用 foo2()，它需要 O(n^3 + m^2)。你觉得 fun2 的时间复杂度是多少？我的猜测是 O(n^3 + m^2 + 2n^2) ！

 int fun2(int n, int G[MAX][MAX])
 {
   int x, y, i, j;
   int ans = y = 0;
   int arr[MAX][MAX] = {};
   for(i = 0; i < n; i++) {
     for(j = 0; j < n; j++)
       arr[i][j] = G[i][j];
   }

   if(n <= 2)
     return 0;
   for(x = 0; x < n; x++){
     if(arr[y][x] && arr[x][y]){
       arr[y][x] = arr[x][y] = 0;
       arr[n+1][x] = arr[x][n+1] = 1;
       arr[y][n] = arr[n][y] = 1;
       if(foo2(n+2, arr))
         ans = 1;
       arr[n][y] = arr[y][n] = 0;
       arr[n+1][x] = arr[x][n+1] = 0;
       arr[y][x] = arr[x][y] = 1;
       if(ans == 1)
         break;
     }    
   }
   return ans;
  }

我对吗？

Answer 1

因为fun1()，我不同意你的看法。在函数体中有一个 for 循环，它采用 O(n) 和 then foo1(n+1, G)，它采用 O((n+1) ⁶ + m ⁴ )。将它们放在一起，我们得到：

O(n) + O((n+1) ⁶ + m ⁴ ) = O(n) + O(n ⁶ + m ⁴ ) = O(n ⁶ + m ⁴ )

---

恐怕我也不同意你的第二个猜测，因为你有两个 for 循环，这让你猜到了你的猜测。

但是，请注意第二个for 循环foo2(n+2, arr)在其主体中调用。结果，foo2()将被称为n倍！

把所有东西放在一起，我们有：

第一个 for 循环 + 第二个 for 循环 = O(n) + O(n(n + 2) ³ + nm ² ) = O(n) + O(n ⁴ + nm ² ) = O(n ⁴ + nm ² )