複雜的二叉樹功能maxheight

MAX-HEIGHT(node) 
    if(node == NIL) 
     return -1; 
    else 
    return max(MAX-HEIGHT(node.leftChild), MAX-HEIGHT(node.rightChild)) + 1;

假設我們有N個節點，我們呼籲與MAX-HEIGHT(root).

我認爲這個功能的複雜度爲O（功能N），因爲我們需要訪問每個節點。但是，我不確定，我無法證實它嚴格。請給我一個很好的解釋，爲什麼它是O（N），如果它是O（N），爲什麼不是O（N）。

那麼，什麼是複雜性？

謝謝。

2013-10-05 Want

順便說一句，你可以自定義該樹在內部保持信息，並使其成爲O（1）操作，並重新計算它在樹的修改（一平衡樹，修改後重新計算將是O（log n）操作） –

在一般情況下，對於平衡二叉樹

T(n) = 2T(n/2) + Θ(1);

每次遞歸調用給你一半大小的兩個問題。通過主定理，這將評估爲T（n）=Θ（n）

在最壞的情況下，每個節點只有一個孩子。

T(n) = T(n-1) + Θ(1)

計算結果爲T（N）=Θ（N）

2013-10-05 21:34:59 sanz

這不是最正式的答案，但必須足夠證明。 – sanz

這是一個很好的答案，因爲你使用主定理（沒有顯示步驟）來證明它。 –

你應該問的問題是：

這裏，N表示樹中節點的數量，並且在返回高度之前必須遍歷所有節點。

出於這個原因，你的算法是O（N）

2015-12-09 14:18:04

回答