首页 > 试题广场 >

如下程序的时间复杂度为？

[单选题]
如下程序的时间复杂度为（其中m>1,e>0）（）
x = m;
y = 1;
while （x - y > e）
{
    x = (x + y) / 2;
    y = m / x;
}
print(x);


	



  • log(m)
  • m^2
  • m^(1/2)
  • m^(1/3)
查看答案及解析
添加回答
推荐
你正年轻头像 你正年轻
A
算法的时间复杂度O（n）,在n比较小的时候，规律不明显。想象一下，logX,X1/2,X1/3函数的曲线，在x比较小时区别不大。但是当x比较大时差别比较明显。
所以我们在取m>1,e>0时，不妨将m取较大数，e取较小数(当m较大时e相当于0)。然后看函数内部执行。
x=m,y=1;
x-y>0;

1.x=(x+y)/2=(m+1)/2 m非常大，则 x=m/2;
y=m/x, x=m/2 则 y=2;

2.x=(x+y)/2=(m/2+2)/2=m/4+1 m非常大，则 x=m/4;
y=m/x, x=m/4 则 y=4;

3.x=(x+y)/2=(m/4+4)/2=m/8+2 m非常大，则 x=m/8;
y=m/x, x=m/8 则 y=8;

.........

x=m/2n,y=2n
当x-y=m/2 n -2 n=0时 m/2 n -2 n=0 m=22n => n=(logm)/2


编辑于 2015-07-01 10:38:58 回复(9)
武岩头像 武岩
举几个例子
发表于 2016-09-04 10:13:26 回复(0)
huixieqingchun头像 huixieqingchun
取大数来判定。
发表于 2016-05-11 22:02:57 回复(0)
mrMask头像 mrMask
推一步 比较两次x-y 比值是2+4/（m-1）
发表于 2017-11-19 14:02:51 回复(0)
任我游头像 任我游
本题的代码实际上表示的是求平方根的算法。而迭代的次数为被二除的次数。
发表于 2017-08-05 10:52:35 回复(0)
牛客887706995号头像 牛客887706995号
其实可以蒙题的，m在小于e+1时代码都直接结束，所以时间复杂度前半段一定是一直为常数，后面慢慢增高，并且可以得出增加的斜率降低，就直接蒙log函数了
发表于 2023-07-11 21:05:04 回复(0)
雨雨雨雨学不完头像 雨雨雨雨学不完
看不懂
发表于 2022-09-17 00:08:18 回复(0)
(ノ=Д=)ノ┻━┻！头像 (ノ=Д=)ノ┻━┻！
话说，可以这么想嘛，m较大时，可以理解为x为一个序列的中间的元素，e是要插入的数，整个操作可看作是二分法？（不知道对不对，但是用这方法蒙对了答案hhhhhh）
发表于 2021-07-06 22:41:25 回复(0)
ML_ZDD头像 ML_ZDD
代码实际就是求m的平方根
发表于 2020-01-15 10:04:15 回复(0)
SHIBO头像 SHIBO
看不懂
发表于 2018-04-09 11:21:49 回复(0)
提交观点

问题信息

复杂度 京东
来自：京东2015校园招聘技...
上传者：小牧魔法袋
难度：
10条回答 15043浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号