首页 > 试题广场 >

假设n为2的乘幂，并且n2，试求下列算法的时间复杂度及变量

[问答题]

假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。

int Time(int n) {
 count = 0;    x=2;
 while(x<n/2) {
 x *= 2;    count++;
 }
 return count;
 }

推荐

赞花婆

发表于 2018-05-05 22:20:46 回复(0)

wcz2023

<p>设n=2^k，m为循环体执行次数。循环条件2^m<2^k-1，即m=1,2,...,k-2 即logn-2</p>

发表于 2020-06-01 14:21:23 回复(0)

独行侠客

每循环一次x值为原来2倍。x原值为2，循环k次后x值为2^k*2。当x<n/2时停止循环，即2^k*2>=n/2,解得k=log(2)n-2。因此时间复杂度为O(log(2)n)。

发表于 2023-07-16 15:23:43 回复(0)

提交观点

问题信息

上传者：赞花婆

难度：

3条回答 12收藏 6637浏览

扫一扫，把题目装进口袋