首页 > 试题广场 >

现有如下代码段: x = 2; &n...

[单选题]

现有如下代码段:

   x = 2;
   while(x<n/2) 
          x = 2*x;

假设n>=0,则其时间复杂度为(   )

  • O(log(n))
  • O(nlog(n))
  • O(n)
  • O(n^2)

1、时间复杂度

1时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

2时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)T(n)的同数量级函数。记作T(n)=(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

x = 2;       ①

   while(x<n/2)

          x = 2*x;    ②

语句①的频度是1,设语句2的频度是f(n),则2^f(n)<=n/2;f(n)<=log2(n/2)近似等于f(n)<=log2(n),取最大值f(n)=log2(n),T(n)=O(log2(n))


发表于 2019-08-07 20:50:19 回复(1)

2*2^X<n/2;

4*2^X<n

2^X+2<n

Log2N<x+2

发表于 2020-07-25 17:21:46 回复(0)
就二分算法的复杂度啊
发表于 2019-08-18 15:33:02 回复(1)

编辑于 2019-10-05 13:06:29 回复(15)
初始条件是x=2,循环终止的条件是x>=n/2,执行一次循环,x就乘以2,所以执行t次循环后,x的值为2的t+1次方,若此时达到终止条件,则2的t+1次方=n/2。
发表于 2019-08-05 20:29:34 回复(7)
求一段程序的时间复杂度 T(n),第一步:找到基本操作和问题的规模;第二步:求出基本操作的执行次数 t = f(n),其中 n 为问题的规模;第三步:求得程序得时间复杂度 T(n) = O(f(n))。
比如求这个题目得时间复杂度 T(n),第一步:基本操作为 while 循环中的语句,问题的规模为 n;第二步:基本操作的执行次数 t 满足 2^(t + 1) >= n / 2,求的 t >= log2(n) - 2;第三步:程序的时间复杂度 T(n) = O(f(n)) = O(log2(n) - 2) = O(log2(n))。
发表于 2020-07-13 14:50:36 回复(1)
这时间复杂度怎么学啊,一点头绪都没有,看公式也有点蒙
发表于 2021-04-13 09:04:49 回复(2)
<p>ji</p>
发表于 2020-11-18 18:19:02 回复(0)
随着数据规模n的不断增加,本题目中的可重复操作执行次数的增加为log2n。 x=2,条件要求当xくn/2时执行,也就是当x>=n/2时程序满足条件结束。 可重复操作为x=2*x,因为变量x的初始值为2,可以认为每次操作都是2的次方上加一,所以2*x等同于2^t(t为执行次数). 2^t>=n/2-->log2(n/2)=t-->log2n-log22=t-->log2n-1=t 近似为log2n=t,也就是当数据规模n增加时,可重复操作执行次数t以log2n的速度增加。
编辑于 2020-10-11 15:33:29 回复(1)
2*2^X
发表于 2021-08-15 21:58:41 回复(0)
时间复杂度和对数的概念。
时间复杂度为O(n),就代表数据量增大几倍,耗时也增大几倍。

时间复杂度O(n^2),就代表数据量增大n倍时,耗时增大n的平方倍,这是比线性更高的时间复杂度。

O(logn),当数据增大n倍时,耗时增大logn(2位底数)
对数:
对数2^3=8那么3=log28   3是8以2位底的对数,2是底数,8是真数。

发表于 2021-08-14 17:20:46 回复(0)
感觉我对时间空间复杂度掌握的还是不够啊,还得加强学习。
发表于 2021-03-05 17:59:09 回复(0)
时间复杂度,就算n趋于∞,那么n/2也是趋于无穷的,所以只和x有关
发表于 2021-03-01 18:38:16 回复(0)
我要回中学学数学咯
发表于 2020-10-16 22:11:44 回复(0)
n/2 其实没有什么有用
发表于 2020-07-19 13:13:05 回复(1)