i=1; while (i<=n) i=i*2 来问下这个这个循环的算法复杂度是多少哈？教教详细过程喔。。 答案是lg n/llg 2

i=1; while (i<=n) i=i*2 来问下这个这个循环的算法复杂度是多少哈？教教详细过程喔。。 答案是lg n/llg 2

答案没错。 i是这样变化的：1， 2, 4, 8, 16, ... 如果用i(x)表示第x次循环时i的值，则 i(x) = 2^x , x初始值为0。 循环在 i <= n 的时候停止，即 i（x) = 2 ^ x <= n; => x<= log2(n) 即循环结束时，最多进行了log2(n)次运算。 按照大O表示法定义，它的复杂度为 O(log2(n)), 即 O(lgn/lg2)

这个明明就是O(n)嘛

复杂度就是判断i何时大于n嘛，即2^i>n，所以运行次数为：log2(n)，可变为 lgn/lg2

你好！ i的取值是1,2,4,8,...直到其值取超过n的2的k次幂， 而这时经哗涪糕皇蕹郝革酮宫捆过了k次循环，时间复杂度就是k。 不难看出k=log2(n)=lgn/lg2 打字不易，采纳哦！