code-complexity - 测量递归函数的代码复杂度

Question

据我的教授说，这段代码是 Teta(n^n)

逐行测量我无法发现自己为什么它的 n^n 复杂性

这是代码

any(v[], n, degree){
   for(i=0; i<degree; i++){
      any(v,n-1,degree)
   }
}

我一直在做自己。

any(v[], n, degree){
   for(i=0 - C; i<degree c(n+1); i++ cn){ 
      any(v,n-1,degree) n(T(n-1))
   }
}

它是2c+2cn+n(T(n-1))。

score 1 · Accepted Answer

您的教授是对的，该代码将永远运行递归地调用自己并且n变得负面。如果这不是您想要的，那么您将必须实现一个条件来结束递归，即 n 的值：

any(v[], n, degree){
   if (n > -1) {
       for(i=0;i< degree;i++){
          any(v,n-1,degree)
       }
   }
}

score 1 · Accepted Answer

首先，看起来这实际上是无限的，因为它不会在 n==0 处中断或返回。假设算法确实在 n==0 处返回（它必须在当前缺失的 if 语句中返回）：

T(n) = 度数*T(n-1)，其中 T(0) = 1 且 T(1) = 度数

这减少到 O(degree^n)

我不太确定 n^n 来自哪里。除非我算错了。

2 回答 2