早教吧作业答案频道 -->数学-->
怎么求算法的时间复杂性的上界和下界?如题估算下列程序段所代表的算法的时间复杂性的上界和下界:(1)for(i=1;i1){if(n%2)n=n-1;elsen=n/2;
题目详情
怎么求算法的时间复杂性的上界和下界?
如题
估算下列程序段所代表的算法的时间复杂性的上界和下界:
(1)for(i=1;i1){if(n%2) n=n-1;else n=n/2;
如题
估算下列程序段所代表的算法的时间复杂性的上界和下界:
(1)for(i=1;i1){if(n%2) n=n-1;else n=n/2;
▼优质解答
答案和解析
简单一点,忽略诸如程序在循环变量上的开销,只考虑循环体
复杂度是通过数运算次数直接数出来的,要知道循环多少次,以及每次循环的工作量
(1)循环n次,每次两步加法两步赋值,简单一点讲就是每次循环工作量都是常数,所以复杂度就是Θ(n)(既是上界也是下界)
对于(2)而言,n=n-1下降比较慢,n=n/2下降比较快,同样每次循环的工作量都是常数,只要看循环次数,所以从前者去统计上界,从后者统计下界
最少的情况来自n=2^k的形式,要循环k步,复杂度下界是Ω(log n)
循环次数比较多的情况是反复出现n=n-1运算的情况,但注意一旦执行该运算之后n一定变成偶数,所以最坏情况是n=n-1和n=n/2交替出现,此时循环次数不超过2log_2 n,复杂度上界是O(log n)
合并起来总体的复杂度还是Θ(n)
复杂度是通过数运算次数直接数出来的,要知道循环多少次,以及每次循环的工作量
(1)循环n次,每次两步加法两步赋值,简单一点讲就是每次循环工作量都是常数,所以复杂度就是Θ(n)(既是上界也是下界)
对于(2)而言,n=n-1下降比较慢,n=n/2下降比较快,同样每次循环的工作量都是常数,只要看循环次数,所以从前者去统计上界,从后者统计下界
最少的情况来自n=2^k的形式,要循环k步,复杂度下界是Ω(log n)
循环次数比较多的情况是反复出现n=n-1运算的情况,但注意一旦执行该运算之后n一定变成偶数,所以最坏情况是n=n-1和n=n/2交替出现,此时循环次数不超过2log_2 n,复杂度上界是O(log n)
合并起来总体的复杂度还是Θ(n)
看了 怎么求算法的时间复杂性的上界...的网友还看了以下:
inti,j,e,f,s,r,k,sum=0,a,b,i1,j1,t,t1,t2;t1=-(10* 2020-05-13 …
根号3除以1-i1/(√3-i)这个复数在复平面内是第几象限?应该是“1除以(√3-i)” 2020-06-12 …
已知复数z=(1+i1-i)2016+(1-i)2(其中i为虚数单位).若复数z的共扼复数为.z, 2020-06-14 …
怎么求算法的时间复杂性的上界和下界?如题估算下列程序段所代表的算法的时间复杂性的上界和下界:(1) 2020-06-22 …
在括号里填上用"珍"组字的词,不可重复1、时光一去不复返,我们要格外(),不能虚度年华 2020-07-11 …
autohotkey脚本IF语句问题实践证明以下这个脚本在满足if的条件时,执行了Click,66 2020-07-18 …
求助EXCLE出现#VALUE!N22的公式为=IF(B22=1,E22,IF(B22=2,E22 2020-07-22 …
设x1=2t+it-1×2t-1+it-2×2t-2+it-3×2t-3+…i2×22+i1×21 2020-07-22 …
已知命题p:“a>0,b>0”是“方程ax2+by2=1”表示椭圆的充要条件;q:在复平面内,复数 2020-08-01 …
数学问题求解1.在同一平面内,直线I1和直线I2满足下列条件:(1)I1与I2没有公共点,则I1与I 2021-01-04 …