单选题
设n是描述问题规模的正整数，下面程序片段的时间复杂度是______。
i=2;
while(i＜n/3)
i=i*3;
A．O(log 2 n)
B．O(n)
C．
i=2;
while(i＜n/3)
i=i*3;
A．O(log 2 n)
B．O(n)
C．
【正确答案】
A
【答案解析】[解析] 考查时间复杂度。在程序中，执行频率最高的语句为“i=i*3”。设该基本语句一共执行了k次，根据循环结束条件，有n＞2*3
k
≥n/3，由此可得算法的时间复杂度为O(log
3
n)=O(lgn)=O(log
2
n)。
注：题中k=log 3 n，又因log 3 n=lgn/lg3，即k的数量级为lgn，由此可知，在时间复杂度为对数级别的时候，底数数字的改变对于整个时间复杂度没有影响，也可一律忽略底数写为O(log 2 n)。
注：题中k=log 3 n，又因log 3 n=lgn/lg3，即k的数量级为lgn，由此可知，在时间复杂度为对数级别的时候，底数数字的改变对于整个时间复杂度没有影响，也可一律忽略底数写为O(log 2 n)。