i=1； while（i<=n） i=i*2； 问时间复杂度为多少？为什么答案为O（log（2）n）？

Question

假设n=8，那么第一次循环后，i=2,第二次循环i=4，第三次i=8，第四次i=8<=8成立，然后i=16，第五次16>8不成立，循环结束，那么这时候循环进行了4次，那么时间复杂度应该是4，但是log2（8）=3，这是为什么？搞不清楚唉。。。求解释

Answer 1

按数量级递增排列，常见的时间复杂度有：
常数阶O(1),对数阶O(log2n),线性阶O(n),
线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，
k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
1、一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f(n)，因此，算法的时间复杂度记做：T(n)=O(f(n))
分析：随着模块n的增大，算法执行的时间的增长率和 f(n) 的增长率成正比，所以 f(n) 越小，算法的时间复杂度越低，算法的效率越高。
2、在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级（它的同数量级有以下：1，log(2)n，n，n log(2)n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))

追问

你讲的太深奥，看不懂，能否用你的方法解答一下这个题目，而且你这样说我的疑问也没有解除呀。。。

Answer 2

在这个程序中，假设要运行y次，则i=i*2^y，由于i≤n，所以i*2^y≤n，考虑到i作为常数对比2的幂级数可忽略，得出最多运行2^y=n，则y=log2 n的结论。我初学，自己瞎琢磨，勿喷

Answer 3

时间复杂度为T(n),O(f(n))叫做渐进时间复杂度。
当n趋近于无穷大时，T(n)=O(f(n))。此时O(f(n))也可叫时间复杂度。且lim T(n)/O(f(n))=常数，表示两者的数量级相同。因此本题中，无论f(n)=log2(n)或=log2(n)+1，lim T(n)/O(f(n))都等于常数，也就是说T(n)=O(f(n))，后者可以代表时间复杂度。而答案为了方便简洁而写成log2(n).

Answer 4

i的值规律：
1，2，4，8，16……
初始i=1(2的0次)，所以i的变化实际是2的x次，所以就是求式子2^x=n，x=log(2)n

Answer 5

假设n=8，那么第一次循环后，i=2,第二次循环i=4，第三次i=8,第四次i=16

追问

你这不等于没回答我的问题嘛。。。不是四次循环吗？时间复杂度不应该是4，那为什么答案是3

追答

我的理解是时间复杂度要看有没有操作，看看循环内部计算了几次，你这个循环只执行了3次i=i*2。

追问

我就是想不通为什么执行了3次，第一次执行i=2,第二次执行i=4,第三次执行i=8，然后因为8<=8，不是又要执行一次嘛？第四次i=16，这不是一共是四次吗？唉。。。理解有些困难、、求大神解答清楚点嘛。。。

追答

我的理解是：
首先时间复杂度是在数量级上衡量一个算法的好坏，log2(n)，n在数量级上不是一个层次；
其次就你的问题来看，i=16的时候程序并没有执行任何操作，所以这次可以忽略不计算在内；
这是我的理解，仅供参考。