algorithm - 创建BST的时间复杂度

Question

在创建 n 节点的二叉堆的情况下，考虑到在任何高度 h 都会有 atmax 这一事实，它的时间复杂度是 O(n) 而不是 nlog(n)

具有 的节点最多需要 O(h) 时间来堆化。

类似地，我想证明 BST 的创建。为此，我使用了这样一个事实，即在任何深度 d 处最多可以有 2^d 个节点，这将花费 atmax O(d) 时间来插入。所以方程式是

为什么这个等式会导致 nlog(n) - BST 创建的预期时间复杂度或 O(n^2) - 最坏情况复杂度。请提出一种如何从上述等式进一步进行的方法。

Answer 1

最后我解决了那个系列。

令 T=log(N) 即 2^T = N(节点数)......................(1)
问题变为 Summation_of(2^d * d) 其中 d 的范围从 o 到 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 log (N)(考虑平衡树)