求解：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 
... 

这类似于一个geometric serie。

逸岸作为

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。

解决这个使用master theorem其中：

• 一个= 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)