杭州交通信息网vmware如何创建虚拟机:关于两道计算机三级偏软“算法”的问题
来源：百度文库 编辑：杭州交通信息网 时间：2024/05/02 09:07:59
1、算法的主运算如下，其中i的初始值为1，s的初始值为0，“←”为赋值号。
While i < n do
{ for j ←1 to n do
s ←s +[i,j];
i←i*2;
}
则该算的时间复杂度为？
A、O（2n） B、（n+Log2n） C、O（nLog2n） D、（n2）
2、计算多项式pn(x)=anxn+an-1xn-1+…+a1x+a0的算法如下，其中“←”为赋值号，该算法的时间复杂度为？
p←a[0];
i←1;t←1;
while i<=n do
{t←t*x;
p←p+a[i]*t;
i←i+1
}
该算法的时间复杂度为？
A、O（n）B、O（Log2n）C、O（nLog2n） D、（n2）
不行啊 这样看Log时不方便
我弄个连接吧
http://photo.163.com/openpic.php?user=xiaoqianggf&pid=853220560&_dir=%2F32115543
http://photo.163.com/openpic.php?user=xiaoqianggf&pid=853220609&_dir=%2F32115543
希望大家能帮忙讲详细一点
更好的是留下QQ或加我QQ指导我
谢谢
还会追加分的
我的QQ 26042449
While i < n do
{ for j ←1 to n do
s ←s +[i,j];
i←i*2;
}
则该算的时间复杂度为？
A、O（2n） B、（n+Log2n） C、O（nLog2n） D、（n2）
2、计算多项式pn(x)=anxn+an-1xn-1+…+a1x+a0的算法如下，其中“←”为赋值号，该算法的时间复杂度为？
p←a[0];
i←1;t←1;
while i<=n do
{t←t*x;
p←p+a[i]*t;
i←i+1
}
该算法的时间复杂度为？
A、O（n）B、O（Log2n）C、O（nLog2n） D、（n2）
不行啊 这样看Log时不方便
我弄个连接吧
http://photo.163.com/openpic.php?user=xiaoqianggf&pid=853220560&_dir=%2F32115543
http://photo.163.com/openpic.php?user=xiaoqianggf&pid=853220609&_dir=%2F32115543
希望大家能帮忙讲详细一点
更好的是留下QQ或加我QQ指导我
谢谢
还会追加分的
我的QQ 26042449
1)C
2)A
只要分析循环变量就行了，赋值的语句都不用管。
1.外层i因为i=i*2的语句，是log2n,内层j=1 to n是n
内外层相乘得n*log2n
其实A和B的答案都形式不对的，不用考虑。
2 i=i+1 i从1增到n，循环执行了N次，是O(n)
C A
链接没有看！不过上面答案肯定正确
楼上的正解
1B,2C,我是这样做的
不懂