单选题
6.
设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
【答案解析】
这是一个比较有趣的问题。如果不仔细分析的话，可能会得到O(n)的结果。
关键在于分析出while语句执行的次数。由于循环体中，i=i*2，所以循环执行的次数是log
2
n，由此可见，算法的时间复杂度不是由问题规模n直接决定，而是log
2
n。
提交答案
关闭