注册 登录
编程论坛 数据结构与算法

算法时间复杂度分析,求上界下界

黄昏黄昏 发布于 2015-03-06 20:00, 4808 次点击
这是书上的一道题:下面的算法段用于确定n的初始值。试分析该算法段所需计算时间的上界和下界。
While(n>1)                //  ----- 1
    If (odd(n))       //  ----- 2
       n=3*n+1        //  ----- 3
    else              //  ----- 4
      n=n/2;          //  ----- 5
最小复杂度:logN,当N=2^m时,只执行第5行代码,
最大复杂度:klog(3N);N约等于[log(N*3^k)]。

上面是找到的答案,最小复杂度可以理解,请问最大复杂度是怎么计算的?
1 回复
#2
黄昏黄昏2015-03-08 18:07
找到答案了,这是3n+1问题,时间复杂度下界是lbN,上界未知,现在还没有答案,所以我找到的那个最大复杂度并不一定正确。
1