algorithm - Big-Theta(n^m) 递归

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) = 恒定时间，我得到T(i) = n^m. 所以我认为我的第二个解决方案是正确的，但我不知道我的第一个解决方案有什么问题。

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), where i = 0, ..., m。