单选题
适中
#12996
以下代码的时间复杂度为?( ) for(int step=1; step<n; step=step*2){ std::cout <<step<<"\n"; }
以下代码的时间复杂度为?( )
for(int step=1; step<n; step=step*2){
std::cout <<step<<"\n";
}
答案与解析
正确答案:C
解析
循环变量 step 从 1 开始,每次乘以 2,直到不再小于 n。
循环停止条件:2^{k-1} < n,可以推出: k-1 < log n,因此时间复杂度是 O(log n)。