algorithm - 递归与非递归小算法的时空复杂度

Question

考虑两个函数，它们接受一个无符号整数作为参数并返回该数字的位数。一个函数是递归的，另一个是非递归的。

就复杂性而言，哪个实现更好？

使用的语言是 C/C++。

这是非递归函数：

int nbOfDigitsNR(int nb) {
int i=0
while(nb!=0){
 nb=nb/10; 
 ++i;
}
return i; // i is the number of digits 
}

递归函数：

int nbOfDigitsNR(int nb) {
 static int i;
 if (nb!=0){
 i=i+1;
 nbOfDigitsNR(nb/10);}
 return i;
}

我建议时间复杂度相同：O(n)，空间复杂度不同：O(n)递归。O(1) 非递归。

Answer 1

说一个函数是递归的还是非递归的并不能告诉我们它的复杂性。

它可能是相等的，或者其中一个复杂度较低。这完全取决于算法。

我有一辆蓝色和一辆灰色的车。哪个更快？

Answer 2

如果一种解决方案是递归的，而另一种是迭代的，那么时间复杂度应该是相同的，当然，如果这是相同的算法实现了两次——一次是递归的，一次是迭代的。

不同之处在于空间复杂性以及编程语言（在您的情况下为 C++）如何处理递归。

你的例子正好说明了这一点。这两个函数将具有相同的时间复杂度，而递归函数将具有更大的空间复杂度，因为 C++ 为堆栈上的每个递归调用分配变量。

如果 n 代表位数，那么您对时间和空间复杂性的看法是正确的。如果 n 代表整数，则将其替换为 lg(n)。