如何計算樹中給定算法的節點數量？

Question

我有一個問題，我需要幫助。我給出了：

int sum(int[] array, int first, int last) 
{ 
if (first == last) 
return array[first]; 
int mid = (first + last)/2; 
return sum(array, first, mid) + sum(array, mid + 1, last); 
} 

問題：確定一個計算遞歸樹中節點數的公式。

所以，我得到的遞歸等式： T（N）= 2T（N/2）+ DN

而且例如用於長度爲8的中遞歸樹的陣列，節點的數目將是15 ，這表明樹中節點的數量是2n-1，其中n是數組的大小。

我想知道我的想法是否正確，並且2n-1公式能否適用於任何情況？另外，有沒有一種通用的方法來計算遞歸樹中給定遞歸算法的節點數？

謝謝你的幫助！

Answer 1

 2 
    /\ 
    1 1 // 2(n) - 1 = 2(2) - 1 = 3 seems to match! 

     3 
    /\ 
    2 1 
/\ 
    1 1  // 2(n) - 1 = 2(3) - 1 = 5 which seems to match 

計算一些其他的例子，公式2（n） - 1似乎是正確的。