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

我有一个fun1调用，它接受foo1()。你认为O(n^6 + m^4)的时间复杂度如何？我猜会是fun1！啊！

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;
  }

我说得对吗？

最佳答案

我不同意你的看法在函数体中有一个for循环，取o（n）然后fun1()，取o（（n+1）6+m4）。把它们放在一起，我们得到：
O（n）+O（（n+1）6+m4）=O（n）+O（n6+m4）=O（n6+m4）
恐怕我也不同意你的第二个猜测，因为你有两个for循环，这使你猜到了你猜到的。
但是，请注意，第二个for-loop调用其主体中的foo1(n+1, G)。因此，foo2(n+2, arr)将被调用foo2()次！
把所有的东西放在一起，我们有：
第一个用于循环+第二个用于循环=o（n）+o（n（n+2）3+
nm2）=O（n）+O（n4+nm2）=O（n4+nm2）