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) 然后是 foo1(n+1, G)，后者采用 O((n+1)⁶ + m⁴).将它们放在一起，我们得到:

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

---

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

但是，请注意第二个for-loop在其主体中调用 foo2(n+2, arr)。结果，foo2() 将被调用 n 次!

将所有内容放在一起，我们有:

first for loop + second for loop = O(n) + O(n(n + 2)³ + nm²) = O(n) + O(n⁴ + nm²) = O(n⁴ + nm²)