2. 考研
  3. 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是_______。 x=2； while(x＜n／2) x=2*x；

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是_______。 x=2； while(x＜n／2) x=2*x；

admin2015-12-30  28
问题 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是_______。
x=2；
while(x＜n／2)
x=2*x；
选项 A、O(log2n)
B、O(n)
C、O(nlog2n)
D、O(n2)
答案A
解析 在程序中，执行频率最高的语句为“x=2*x”。设该语句共执行了T(n)次，则2T(n)+1＜n／2，故T(n)=log2(n／2)-1=log2n-2，得T(n)=O(log2n)。
转载请注明原文地址:https://kaotiyun.com/show/G7xi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)