i  =  n*n;
 while(i!=1)
    i = i / 2;
高手们帮忙说下复杂度吧。自己想了半天不会。

O（以2为底数 n平方的对数）

O(logn)

怎么推导出的？

循环需要的进行的次数m，满足：

2^m=n^2

符号^表示乘方

对于数据结构的知识，我了解的不是太多，我不知道O（n）和O（2n）是不是相同的意思，如果是的话，可以化简成
O（log n）

那个指数2没必要保留，直接写成O(logn)就行了，不需要加个平方

蛤蟆跳井---不懂，再详细点吧

系数不用考虑，怎么导出的呢？

i  =  n*n;
while(i!=1)
    i = i / 2;
逆向思维
for(i=1;i<=n*n;)
{
  i = i*2;
}这个时间复杂度表示什么-就是2^n = m,那么2^n=m反函数就是log2 m =n,将程序反转来想就是 O(logm)

[ 本帖最后由 点线面 于 2011-1-17 20:36 编辑 ]

收到的鲜花

• 逐渐学习 于 2011-01-17 20:48 送鲜花  5朵   附言：我很赞同