for(i=n;i>=1;i*=2)

for(i=n;i>=1;i*=2)
请有知道的朋友回答下,下面语句的时间复杂度:
for(i=n;i>=1;i*=2);
这是我遇到的一个问题,觉得无从理解.
piaoyao220 1年前 已收到1个回答 举报

hongmei_tan 幼苗

共回答了18个问题采纳率:94.4% 举报

for(i=m;i>=1;i*=2);
当m小于等于0时,只判断了一次便退出循环,时间复杂度为1;
当m大于等于1时,时间复杂度为n,但是由于i永远大于等于1,这个循环是个死循环,n为无穷大.
计算方法
1. 一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n))
分析:随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高.
2. 在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度T(n)=O(f(n))
例:算法:
for(i=1;i

1年前

7
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.024 s. - webmaster@yulucn.com