BST創建的時間複雜度

與n節點的二進制堆創建的情況一樣，考慮到在任何高度h都將存在的事實，其時間複雜度證明是O（n）而不是nlog（n），這將是atmaxBST創建的時間複雜度

$\frac{n}{2^{h+1}}$

節點將需要最多O（h）時間heapify。

$\sum_{h=0}^{log(n)}\frac{n}{2^{h+1}}*O(h)=O(n)$

在類似的路線，我想證明BST的創建。爲此，我使用的事實是，在任何深度d處都可能有最多2^d節點，這將花費最多O（d）時間來插入。因此，公式將

$\sum_{d=0}^{log(n)}{2^d}*O(d)$

這個公式怎麼會導致NLOG（n）的BST創建或者爲O（n^2）-worst情況複雜的-expected時間複雜度。請提出一個方法，如何從上面的等式進一步進行。

來源

2016-05-31 Deepankar Singh

你的數學不正確。你的款項出錯了，因爲大多數節點都插在更深處。創建一個二進制堆是O（N），因爲使用了自下而上的結構，而不是插入每個元素並對其進行堆積。如果你必須獨立地插入每一個，它將是O（N log N）。 –

這裏有什麼不對的地方請指出，對於n節點bst atleast層（log（n）） - 高度是必需的，在每個深度d它將有2^d個節點，考慮15節點高度的平衡bst出來是floor（log（15）），即3，在level-3中它將有2^3個節點，即8個節點。對於插入場景，所有8個節點將不得不下降到最後一級，從而產生2^d * h種方程。如果這是錯誤的我在這裏失蹤？ –

h，d和n是相關的。這樣做更容易：半節點將插入深度log（n），所以如果插入花費的時間與深度成正比，那麼總插入時間> = O（0.5 n log n）> = O（n log N）。同樣，所有的節點將被插入深度<= log（n），所以總時間是<= O（n log n） –

最後我解決了那個系列。（1）
問題變成summation_of（2^d * d）其中，（2）其中， d的範圍從0到T.所以

 

    G(T)  = 0*2^0 + 1*2^1 + 2*2^2 + ..... + T*2^T.
 
    2G(T)  =   0*2^1 + 1*2^2 + ..... +(T-1)*2^T + T*2^(T+1) 
 
    2G(T)-G(T) = 0  - 2^1 -2^2 - ..... - 2^T + 2T*2^T
 
    G(T)  =  - 2^(T+1)-2 + 2T*2^T 
    G(T)  = 2((T-1)2^T +1) 
    which is  = 2((log(N)-1)N +1)...........from (1)

因此給出上界如N日誌（N）（考慮平衡樹）

來源

2016-06-02 18:51:55

BST創建的時間複雜度

回答

相關問題