递归func(int a，int n)和返回a*func(a，n-1)的时间复杂度是多少

Question

int func(int a, int n){
if (n==0) return 1;
else return a*func(a,n-1);
}

我在学习算法，我想知道这个函数的时间复杂度是多少？

Answer 1

函数计算a^n。

此函数将在具有不同参数的系统堆栈(分配给程序(上按n次数。

因此，时间复杂度为O(n(。

如果递归对您来说很难可视化，那么可以将其视为类似于使用循环进行计算。循环将运行n多次。

例如：

function power(a, n){    
ans = 1;
for(int i=1; i<=n;i++){
ans = ans * a;
}
return ans;
}

可视化递归的最佳方式：

绘制递归树。