衡量一个递归函数

Question

的代码的复杂性。根据我的教授，这个代码是泰塔（N^N）由线

测量线路，我不能发现自己，为什么它的N 1，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^N从何而来。除非我把数学做错了。

Answer 2

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

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