Big-Theta(n^m) recursive

Question

我试图在Big Theta（n^m）中实现一个具有时间复杂性的算法，n和m是自然数。

我的第一个解决方案：

algo(n,m,i){ // called with algo(n,m,1)
  if (i < m){
   algo(n,m,i+1)
  }
  for i = 1 to n{
    print(do something in constant time);
  }
}

我的第二个解决方案：

algo(n,m,i){ //called with algo(n,m,m)
   if (i > 0){
      for j = 1 to n{
         algo(n,m,i-1)
      }
   }else{
   print(do something in constant time);
   }
}

当我分析我的第二个解决方案，称为algo(n,m,m)时，我得到了T(i) = n * T(i-1), i > 0。当T（0）=恒定时间时，得到CCD_ 3。所以我认为我的第二个解决方案是对的，但我不知道我的第一个解决方案出了什么问题。

Answer 1

对于您的第一个算法，

if (i < m)
    algo(n, m, i+1)

基本上会调用algo，总共调用m * (m-1) / 2次，每个algo都有一个O(n)循环，因此，总复杂度将为O(n * m ^ 2)。

或者换句话说，对于第一个算法，它类似于T(i) = n + T(i-1)，其中i = 0, ..., m。