单选题
设n是描述问题规模的非负整数，下面程序片段的时间复杂度是______。
int i=1;
while (i＜=n)
i=i*2;
A．O(log
2
n) B．O(n) C．O(nlog
2
n) D．O(n
2
)
A
B
C
D
【正确答案】
A
【答案解析】
[解析] 这是一个比较有趣的问题。如果不仔细分析的话，可能会得到O(n)的结果。关键在于分析出while语句执行的次数。由于循环体中，i=i*2，所以循环执行的次数是log
2
n，由此可见，算法的时间复杂度不是由问题规模n直接决定，而是log
2
n。
提交答案
关闭