主题:[讨论]跪求高手解答数据结构问题
第一题: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吗?
小弟刚学数据结构,希望各位不吝赐教!谢谢!
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吗?
小弟刚学数据结构,希望各位不吝赐教!谢谢!