证明递归：证明 M(n) >= 1/2 (n + 1) lg(n + 1)

Question

我想证明快速排序的递归运行在 n log n 上的最佳时间。

我得到了这个递归公式

M(0) = 1
M(1) = 1
M(n) = min (0 <= k <= n-1) {M(K) + M(n - k - 1)} + n

show that M(n) >= 1/2 (n + 1) lg(n + 1)

到目前为止我得到了什么：

By induction hyposes

M(n) <= min {M(k) + M(n - k - 1} + n

专注于我得到的内在表达：

1/2(k + 1)lg(k + 1) + 1/2(n - k)lg(n - k)
1/2lg(k + 1)^(k + 1) + 1/2lg(n - k)^(n - k)
1/2(lg(k + 1)^(k + 1) + lg(n - k)^(n - k)
1/2(lg((k + 1)^(k + 1) . (n - k)^(n - k))

但我觉得我做错了什么。我认为 "k" 应该是 gonne 但我看不出这个等式如何抵消所有 "k"。所以，我可能做错了什么

Answer 1

您确实想摆脱 k。为此，您需要找到 M(k) + M(n - k - 1) 的最小值的下界。一般来说，它可以任意棘手，但在这种情况下，标准方法有效：通过 k.

求导

((k+1) ln(k+1) + (n-k) ln(n-k))' =
ln(k+1) + (k+1)/(k+1) - ln(n-k) - (n-k)/(n-k) =
ln((k+1) / (n-k))

我们希望导数为0，所以

ln((k+1) / (n-k)) = 0 <=>
(k+1) / (n-k) = 1 <=>
k + 1 = n - k <=>
k = (n-1) / 2

您可以检查它是否确实是局部最小值。因此，k=(n-1)/2 达到了 M(k) + M(n - k - 1) 的最佳下界（我们可以从归纳假设中得到）。现在你可以用这个值代替 k，n 将是你唯一剩下的变量。

证明递归：证明 M(n) >= 1/2 (n + 1) lg(n + 1)

Prove recursion: Show that M(n) >= 1/2 (n + 1) lg(n + 1)

recursion

proof