首页 > 试题广场 > 现有如下代码段:    x
[单选题]

现有如下代码段:

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

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

  • O(log2(n))
  • O(nlog2(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)

编辑于 2019-10-05 13:06:29 回复(5)
初始条件是x=2,循环终止的条件是x>=n/2,执行一次循环,x就乘以2,所以执行t次循环后,x的值为2的t+1次方,若此时达到终止条件,则2的t+1次方=n/2。
发表于 2019-08-05 20:29:34 回复(1)
就二分算法的复杂度啊
发表于 2019-08-18 15:33:02 回复(0)