Question

数据结构中的时间复杂度及count的值，求具体的思路和解题过程

设n为2的乘幂,且n>2,试求算法的时间复杂度及count的值。
int Time(int n)
{
count=0;

x=2;
while(x<n/2)

{
x *= 2;
count++;
}
return count

}

Answer 1

初值x=2，count=0，循环条件x<n/2，
第1次，循环条件成立，则x=x*2=2^2，count=count++=1
第2次，循环条件成立，则x=x*2=2^3，count=count++=2
。。。。。
第k-1次，循环条件成立，则x=x*2=2^k，count=count++=k-1
第k次，循环条件成立，即x=2^k<n/2，则x=x*2=2^(k+1)，count=count++=k
由x=2^k<n/2，所以k<log2(n/2)=log2n-1，所以k=log2n-2.
所以算法的时间复杂度为O（log2n）。count的值为log2n-2