求解:T(n)= T(n/2)+ n/2 + 1

Question

我很难用O表示法定义以下算法的运行时间.我的第一个猜测是O(n),但是迭代和我应用的数字之间的差距并不稳定.我怎么错误地定义了这个？

public int function (int n ) 
{
  if ( n == 0) {
    return 0;
  }

  int i = 1;
  int j = n ;
  while ( i < j ) 
  {
    i = i + 1;
    j = j - 1;
  }
  return function ( i - 1) + 1;
}

Answer 1

这while是在大约n/2时间内执行的.

递归作为n一个约为原始值的一半的值传递n,因此:

n/2 (first iteration)
n/4 (second iteration, equal to (n/2)/2)
n/8
n/16
n/32
...

这类似于几何系列.

事实上,它可以表示为

n * (1/2 + 1/4 + 1/8 + 1/16 + ...) 

所以它汇聚到了 n * 1 = n

所以O表示法是O(n)

Answer 2

另一种方法是将其写下来T(n) = T(n/2) + n/2 + 1.
while循环确实n/2有效.传递给下一个电话的论据是n/2.

使用主定理解决这个问题,其中:

• a = 1
• b = 2
• f = n/2 + 1

Let c=0.9
1*(f(n/2) + 1) <? c*f(n)
1*(n/4)+1 <? 0.9*(n/2 + 1)
0.25n + 1 <? 0.45n + 0.9
     0    <  0.2n - 0.1 

这是:

T(n) = ?(n)