顺序插入n个随机元素构建二叉搜索树的时间下界求解

你给出的递推式对应n个节点的二叉搜索树能达到的最小总节点深度，对应的是最优平衡BST的总插入时间成本，两种常用严谨证明方法如下： #

方法1：数学归纳法（代入法） #

上界O(n lg n)证明 #

• 归纳假设：存在正的常数c，对所有k < n，满足 T(k) ≤ c k lg k
• 递推式中的min项由琴生不等式可证，当左右子树节点数尽可能均等时取最小值，即i = ⌊(n-1)/2⌋
• 代入递推式，取n为2的幂次简化计算（非2的幂次可通过夹逼法得到同阶结果）：

  T(n) = n-1 + T(n/2) + T(n/2)
       ≤ n-1 + 2 * c*(n/2) * lg(n/2)
       = n-1 + c n (lg n - 1)
       = c n lg n + (n - 1 - c n)
  

• 取c≥1时，n-1 -c n ≤ 0，因此T(n) ≤ c n lg n，上界成立

下界Ω(n lg n)证明 #

• 归纳假设：存在正的常数c，对所有k <n，满足T(k) ≥ c k lg k
• 同样取均等分割的最小值代入，还是用n为2的幂次计算：

  T(n) = n-1 + T(n/2) + T(n/2)
       ≥ n-1 + 2 * c*(n/2) * lg(n/2)
       = n-1 + c n (lg n - 1)
       = c n lg n + (n - 1 - c n)
  

• 取c=1/2时，n-1 - 0.5n = 0.5n -1 ≥ 0对所有n≥2成立，因此T(n) ≥ 0.5 n lg n，下界成立

上下界合并即可得T(n) = Θ(n lg n) #

方法2：主定理直接推导 #

由于min操作保证每次分割都是最优的对半分，原递推式可以近似等效为标准分治递推：
T(n) = 2T(n/2) + Θ(n)
直接套用主定理的情况2，可直接得到解为Θ(n lg n)，该结果和归纳法得到的结论完全一致。 #

如果你的需求是证明随机插入构建BST的期望时间下界，不是最小总深度的下界，也可以通过概率期望的方法推导，期望总深度同样是Θ(n lg n)量级。

内容的提问来源于stack exchange，提问作者W.Z.Hai