程序段i=1；while(i<=n)i=i*2;的时间的复杂度是（？）

如题所述

举报该问题

推荐答案 2019-05-30

你可以分析i，和循环次数之间的关系
i = 1, 2, 4, 8, 16 ...
所以假设循环次数是x。
那么i = 2^x
条件是i <= n
2^x <= n
所以x <= logn
所以x 从1 到logn，一共执行循环体logn次，所以复杂度是logn

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

当前网址：http://00.wendadaohang.com/zd/0D0ZZB0BjnrTnneeBj.html

第1个回答 2019-05-30

假设循环次数是x。
i = 1, 2, 4, 8, 16 ，i = 2^x
条件是i <= n
2^x <= n
所以x <= log2n 一共执行循环体log2n次，所以复杂度是O(log2n)

相似回答

下面程序段的时间复杂度为___。(n>1)答：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;答：8<n 是 16= 2(4)...2(k-1)<n 是 = 2(k) 最后一次则有2(k) <= n，取“=”，有 2(k) = n，得k = log(2)n 表示以2为底n的对数。去掉较低次方和最高次方的系数，得 时间复杂度 = log(n)

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， 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...

大家正在搜

while和when的区别 while(n++<=2)while(n--)是什么意思程序while什么意思 while循环1加到n的和 while(n)whilen是什么意思用do while求n的阶乘 while在编程里什么意思

i=1; while (i<=n) i=i*2 时间复杂度

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

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

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

程序段“for(i=1; i<=n;) i=i*2;”的时间...

面程序段的时间复杂度是( ) i=1; while(i<=n...

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

求i=1; while(i<=n); i=i+2;的时间复杂...