首页 > 试题广场 >

求其时间复杂度( ) int i = 1, n = 1

[单选题]

求其时间复杂度( )

int i = 1, n = 100;

while(i < n){

    i = i * 2;

} 

  • O(log2n)
  • O(n)
  • O(nlog2n)
  • O(n2)
查看正确选项
添加回答
俺们吃土豆头像 俺们吃土豆
因为每次i*2后，距离结束循环更近了。也就是说有多少个2 相乘后大于n，退出循环。
数学公式：2^x = n    -->     x = log2n
因此这个循环的时间复杂度为O(log2n)   2为log的底数
发表于 2019-02-11 23:30:54 回复(0)
涸辙之鱼201812122013981头像 涸辙之鱼201812122013981
时间复杂度 可以看出循环是 2k次方 k是循环次数，i 的结果是 1 2 4 8 16 32 64 128 8次以后退出循环 那么他的复杂度应该是log(200)  7<log（200）<8 所以时间复杂度log(2n)其他求的都不对 今天看二分法看的时间复杂度 就是得到结果尝试次数 
编辑于 2018-12-13 20:24:56 回复(0)
提交观点

问题信息

2019 有赞 Java工程师
上传者：小小
难度：
2条回答 901浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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