跪求高手解答数据结构问题

menghuann0

第一题：i=1;   

              while(i<=n)

                      i=i*2;              (1)

设语句（1）的频度为f（n），则有：

2^f(n)<=n, 即f(n)<=log  n,
                                            2
取最大值f（n）=log  n.
                       2
请问2^f(n)<=n是怎样得到的？


第二题：
                     a=0;b=1;                             (1)

                     for(i=2;i<=n;i++)              (2)

                     {                                       (3)

                                   s=a+b;               (4)

                                   b=a;                   (5)

                                    a=s;                   (6)

                       }
              其中语句（1）的频度是2；语句（2）的频度是n；语句（3）的频度是n-1；语句（4）的频度是n-1；语句（5）的频度是n-1.则该程序段的时间复杂度是T（n）=2+n+3*(n-1)=4n-1
                请问语句（1）的频度是2是不是因为a=0执行了一次，b=1执行了一次？加起来就是2次？至于语句（2）的频度不应该是n-1吗？语句（3）的频度不应该是n-3吗？

请详细说明，谢

[ 本帖最后由 menghuann0 于 2009-10-24 00:24 编辑 ]