首页 > 试题广场 >

下面程序片段的时间复杂度是（）。

[单选题]

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。

x = 2;
while (x < n / 2) x *= 2;

查看正确选项

超麻烦

设执行k次。则个，2的k-1次方等于n/2

恒等变换 k等于log2 n

发表于 2019-12-04 15:21:35 回复(6)

二咩

每次循环x乘2，所以复杂度是o(log2n)

发表于 2016-12-01 09:11:41 回复(0)

Xindolia_Ring

复杂度是 $O(log_2n)$

在程序中，执行频率最高的语句为“x=2*x;”

设该语句共执行了T(n)次，则2T(n)+1 ≤ n/2，故 $T(n)=log_2(n/2)-1=log_2n-2$ ，得 $T(n)=O(log_2n)$ 。

发表于 2019-04-04 12:14:25 回复(0)

鹏123

准确答案是log(n/4)只不过这个答案也满足

发表于 2017-09-20 16:02:50 回复(0)

牛客700925932号

执行O（n）次，则2的O（n）次方大于等于n/2时结束，因为x为2，所以每执行一次，等于自己多做一次幂运算，复杂度为log（n/2），为A

发表于 2022-02-12 14:30:03 回复(0)

提交观点

问题信息

复杂度

上传者：城市里的养猫者

难度：

5条回答 150收藏 9193浏览

扫一扫，把题目装进口袋