程序段“for(i=1; i<=n;) i=i*2;”的时间复杂度?

答案是：O(log2n

)

i=1

①

while

(i<=n)

i=i*2

②

解：

语句1的频度是1,

设语句2的频度是f(n),

则：2^f(n)<=nf(n)<=log2n

取最大值f(n)=

log2n,

T(n)=O(log2n

)

-------------------------------------------*来源于百

度*---------------------------------------

///////////////////////////////////////////////////////////////////////

修正下：O(log

N)，以免和常用对数混淆

底是多少无关紧要，可以用换底公式换掉

log2N

=

logxN

/

logx2

logx2是个常数，可以被忽略

for (i=2i==0)

printf("%d",i--)

因为i=2一开始就进行条件判断，i==0是否成立，显然不成立，故跳出循环，故循环0次。没有i输出

0次

---