通緝：在階二叉樹輸出方法的遞推公式

我是有點果醬搜索出該Java方法的遞推公式通緝：在階二叉樹輸出方法的遞推公式

void printInorder(Node<T> v) { 
    if(v != null) { 
     printInorder(v.getLeft()); 
     System.out.println(v.getData()); 
     printInorder(v.getRight()); 
    } 
}

一些標準：

其一個完整的二叉樹（每隔內結有2個孩子，每葉有相同的深度）
樹具有n結和一個爲O（n）的複雜性

我必須找到與n knots的樹的depth h相關的遞推公式，作爲額外的獎勵，我需要從中導出O（n）的顯式公式。現在

，這是我的了：

d = depth of the tree 
c = constant runtime for execution of the method itself 
d = 1: T(n) = c 
d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c

我使用的示例d = 3，以澄清事情，我自己也有困難進一步打破下來。我的假設是否正確？

編輯：事物

[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next full number 
d = 1: T(d) = 1 
d > 1: T(d) = 2^(h-1) * T(n/(2^(h-1))) 

1: T(h) = T(i = 0) + T(i = 1) + ... T(i = h-1) 
2: T(h) <= (2^(0-1) + n/(2^(0-1))) + (2^(1-1) + n/(2^(1-1))) + ... + (2^(h-2) + n/(2^(h-2))) 
3: T(h) = n + n + ... + n 
4: T(h) = (h-1)n 
5: T(h) = O(n)

因爲樹深度的每一級包含恰好2 ^（H-1）的節點接着嘗試，在第4行第h因子可以因爲忽略n與最終結果更相關。

來源

2012-07-09 Ben

T（N）= T（N/2）+ T（N/2）+ 1

級別0有1個操作。
1級有2個操作。
2級有4個操作。
等級k有2^k個操作。
樹的深度是lgn。

1 + 2 + ... + 2^LGN =
2^0 + 2^1 + 2^2 + ... + 2^LGN =
（2 ^（LGN + 1 ）-1）/（2-1）= 2 * 2^lgn =
2n。

來源

2012-07-09 12:56:22

下面是一個使用光滑規則（列維京，算法的設計&分析，第二版，481-82），允許遞歸關係的替代方法，如這被表示爲一個指數來代替。

Demonstration of smoothness rule.

任一種方法 - 向前或向後取代 - 適合於這個問題。在很多情況下，我發現後向替代更容易消化。

來源

2012-07-09 13:42:30 Makoto

通緝：在階二叉樹輸出方法的遞推公式

回答

相關問題