解决：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;
}

- sra

---

准确来说，bit-O 用于上界，因此有许多可能的答案。例如，说这个算法是 O(n*n) 是正确的，但有点误导人。如果可能的话，通常最好使用 big-Theta 来说明运行时间。接受答案中的分析对于 big-Theta 同样有效。 - Theodore Norvell

Answer 1

while 的执行时间约为 n/2。

递归是将约为原始值的一半的值作为n传递执行，因此：

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

这类似于等比数列。实际上它可以表示为：

This is similar to a geometric series.

In fact, it can be represented as:

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

因此它收敛于 n * 1 = n

因此O符号表示为 O(n)

- Davide Lorenzo MARINO

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)

- Tony Tannous