设n是描述问题规模的非负整数，下面程序片段的时间复杂度是_______。x=2；while(x＜n／2)x=2*x；
A、
O(log
2
n)
B、
O(n)
C、
O(nlog
2
n)
D、
O(n
2
)
【正确答案】
A
【答案解析】
解析：在程序中，执行频率最高的语句为“x=2*x”。设该语句共执行了T(n)次，则2
T(n)+1
＜n／2，故T(n)=log
2
(n／2)-1=log
2
n-2，得T(n)=O(log
2
n)。
提交答案
关闭