You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

求解递归函数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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.08.19 16:00:26