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