首页 > 试题广场 >

给定一递归算法的程序段如下（n2），则该算法的时间复杂度为

[单选题]

给定一递归算法的程序段如下（n>2），则该算法的时间复杂度为（）。

int fun(int n)
{
    if(n <= 1)
        return 2;
    else
        return fun(n / 2) + n;
}

查看答案及解析

光电管

个人感觉递归方程应该是 T(n)=T(n/2)+1 =T(n/4)+1+1 =T(n/8)+1+1+1 =T(n/16)+1+1+1+1 =T(n/32)+1+1+1+1+1=………..=logn + T(1)=logn+1

发表于 2022-03-15 15:40:34 回复(0)

筱羊冰冰

递归方程是T(n) = T(n/2)+n，和归并是相同的，所以是nlogn

发表于 2022-01-16 11:27:52 回复(3)

YaYaLeSlimTan

T(n)=(1/2)^0*n+(1/2)^1*n+(1/2)^2*n...+(1/2)^n*n；比如n=8，T(n)=8+4+2=2^(n+1)-2；我这样想，有什么问题吗？

发表于 2022-04-03 00:48:03 回复(0)

叉叉L

这道题为什么不能用主定理法？？？

发表于 2022-05-03 12:15:16 回复(0)

牛客863963759号

T(n) = T(n/2) + 1

发表于 2022-05-24 15:45:07 回复(0)

提交观点

问题信息

复杂度递归

难度：

5条回答 88收藏 2017浏览

扫一扫，把题目装进口袋