求解递归函数rec(n)的时间/空间复杂度、返回值与调用次数
递归函数复杂度与返回值分析求助
这是我大二的教材作业题,已经尝试求解3天还是有困难。题目要求分析递归函数rec(n)的时间复杂度(Time Complexity)、空间复杂度(Space Complexity)、返回值的渐近阶以及函数调用次数。
函数代码如下:
rec(n) { if( n <= 2 ) return 1; return 2*rec(sqrt(n)) + 2*rec(sqrt(n)) + log(n); }
我自己推导的结果:
- 时间复杂度:Θ(log n)
- 返回值:Θ(log²n)
- 函数调用次数:Θ(log log n)
- 空间复杂度:Θ(log log n)
希望有人能指出我的错误,并给出正确的推导过程。
内容的提问来源于stack exchange,提问作者Isabella Amdahl
相关产品推荐
相关产品推荐

