回 帖 发 新 帖 刷新版面

主题:[讨论]跪求高手解答数据结构问题

第一题: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吗?
小弟刚学数据结构,希望各位不吝赐教!谢谢!

回复列表 (共2个回复)

沙发

第一题设频度为f(n)是次数,即i=2^f(n)<n

板凳

[quote]第一题设频度为f(n)是次数,即i=2^f(n)<n[/quote]
难道你是传说中的SB,这个不是明摆着的吗?

我来回复

您尚未登录,请登录后再回复。点此登录或注册