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