Question

数据结构算法：求时间复杂度和空间复杂度

下面两个函数fun1和fun2都是实现对整数的逆序输出功能，请根据下面题目要求，给出答案。

（1） 请分析函数fun1的时间复杂度和空间复杂度；

（2） 请分析函数fun2的时间复杂度和空间复杂度。

代码如下：

int fun1(int n)
{
int rev = 0;
while (n != 0) {
int pop = n % 10;
n /= 10;
rev = rev * 10 + pop;
}
return rev;
}

void fun2(int n)
{
printf("%d", n % 10);
if(n / 10 != 0)
fun2(n / 10);
}

int main(void)
{
printf("%d\n", fun1(10203));
fun2(10203);

return 0;
}

Answer 1

(1)
时间复杂度 O(logn)
空间复杂度 O(1)
(2)
时间复杂度 O(logn)
空间复杂度 O(logn)