测量递归函数的代码复杂性

Question

根据我的教授，这个代码是Teta（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))。

Answer 1

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

T（n）=度数*T（n-1），其中T（0）=1，T（1）=度数

这减少到O（度^n）

我真的不确定n从哪里来。除非我数学做错了。

Answer 2

您的教授是对的，该代码将永远递归地调用自己，n为负数。如果这不是你想要的，那么你必须实现一个条件来结束递归，即n:的值

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