分析以下程序的时间复杂度:
i=1;
while(i<=n)
{
i=i*2;
}
解析:

关键是要找出来执行次数x与n的关系,并表示成n=的函数;

具体解析过程:

若循环执行一次:i=1*2=2;
若循环执行两次:i=2*2=2^2;
若循环执行三次:i=2*2*2=2^3;
若循环执行x次:i=2^x
设语句执行x次,由循环条件i<=n,可知:
∵2^x<=n,∴x<=log以2为底的n;