i=1; while (i<=n) i=i*2 来问下这个这个循环的算法复杂度是多少哈？教教详细过程喔。。答案是lg n/llg 2

如题所述

举报该问题

推荐答案 2010-09-10

答案没错。
i是这样变化的：1， 2, 4, 8, 16, ...

如果用i(x)表示第x次循环时i的值，则 i(x) = 2^x , x初始值为0。

循环在 i <= n 的时候停止，即 i（x) = 2 ^ x <= n;

=> x<= log2(n)
即循环结束时，最多进行了log2(n)次运算。

按照大O表示法定义，它的复杂度为 O(log2(n)), 即 O(lgn/lg2)

温馨提示：答案为网友推荐，仅供参考

当前网址：http://77.wendadaohang.com/zd/GpYNNYIqp.html

第1个回答 2010-09-10

i的取值是1,2,4,8,...直到其值取超过n的2的k次幂，
而这时经过了k次循环，时间复杂度就是k。
不难看出k=log2(n)=lgn/lg2

第2个回答 2010-09-10

复杂度就是判断i何时大于n嘛，即2^i>n，所以运行次数为：log2(n)，可变为 lgn/lg2

第3个回答 2010-09-10

这个明明就是O(n)嘛

相似回答

分析下列程序段的时间复杂度是___。 i=1: while(i<=n) i=i*2;答：【答案】：C 循环体里面是i=i*2，即每循环一次i值增加一倍，所以执行次数与n之间是以2为底的对数关系，故时间复杂度为O(log2n)。

i=1; while(i<=n) i=i*2 这个算法的时间复杂度怎么算答：一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f (n)，因此，算法的时间复杂度记做：T (n) =0 (f (n) )。随着模块n的增大，算法执行的时间的增长率和f (n)的增长率成正比，所以f (n)越小，算法的时间复杂度越低，算法的效率越高。在计算时间复杂度的时候，先找出算法的基...

下面程序段的时间复杂度是 ? i=1; while(i<=n) i=i*2答：i=1； while（i<=n） i=i*2的时间复杂度O(log2n)。整段代码语句，中循环体只有一个while（i<=n），执行的次数是：i = 1，i = 1*2=2，判断2是否小于等于n，是则继续循环，否则跳出循环。i =2，i = 2*2=4，判断4是否小于等于n，是则继续循环，否则跳出循环。i =4 ，i = 4*...

写出下列算法的时间复杂度: i=1; while(i<=n) i=i*2;答：第一次对比：i＝2^0 第二次对比：i=2^1 ...第k次对比：i=2^(k-1)..untile 2^(k-1)>n;===>k-1>logn ===>时间复杂度为log(n)

计算机考研科目数据结构中题型求时间复杂度,i=1;while(i<=n)i=i*2;答：分析过程：i 是否执行循环 i --- 1<n 是 2 = 2(1) 表示2的1次方，以下类同 2<n 是 4 = 2(2)4<n 是 8 = 2(3)8<n 是 16= 2(4)...2(k-1)<n 是 = 2(k) 最后一次则有2(k) <= n，取“=”，有 2(k) ...

i=1;while i=i*2;问时间复杂度为多少答：时间复杂度为O(n^0.5)，即根号n的数量级。该程序求解的是：s=1+3+5+7+...+(2k+1)，且使得s-(2k+1)<n≤s。而s=(1+(2k+1))*(k+1)/2=(k+1)^2，k+1则为上述等差数列的项数，也是你的程序中while循环执行的趟数。求出k<根号n≤(k+1)，因此循环执行根号n趟。则T(n)=2...

...while语句编写一个求和程序(即sum=1+2+3+…+n)答：回答：int sum=0;for(int i=1;i<n;i++){sum+=i;}int i=1while(i<n){sum+=i;i++;}do{sum+=i;}while(i++<n);System.out.print(sum);

大家正在搜

while循环1加到n的和 while和when的区别 while(n++<=2)while(n--)是什么意思用do while求n的阶乘 while(n)whilen是什么意思 while(i++<5)int n=5,a[n]

i=1; while(i<=n) i=i*3; 谁能告诉我这...

i=1;while i=i*2;问时间复杂度为多少

i=1； while（i<=n） i=i*2；问时间复杂度...

i=i+1; while(i<=n) i=i*2;分析一下这...

i=1; while(i<=n) i=i*2 这个算法的时间...

下面程序段的时间复杂度是？ i=1； while（i<=n...

i=1; while(i<=n) i=i*3; 谁能告诉我这...

分析下列算法的时间复杂度 void f(int n) { i...