algorithm - SELECT算法分析中的复现

Question

在 CLRS (2/e，第 191 页，第 9.3 节) 中，对用于查找数组中第 i 个最小元素的 SELECT 算法的分析如下所示归纳证明:

1.  T(n) <= c celing(n/5) + c(7n/10 + 6) + an
2.       <= cn/5 + c + 7cn/10 + 6c + an
3.       = 9cn/10 + 7c + an
4.       = cn + (-cn/10 + 7c + an)
5.       = cn,  when -cn/10 + 7c + an <= 0

我理解算法，但证明中的两个操作让我有点难过。

问题 1:在第 2 行中，额外的 c 项是从哪里来的(第二项)？ c 乘以 (7n/10 + 6) 项得到 7cn/10 + 6c。

问题2:在第4行中，我们是如何从9cn/10到cn + (-cn/10 ...)? 9系数哪里去了？

这不是作业

谢谢!

Answer 1

1. 额外的 c 来自 c*celing(n/5) - 考虑 n/5 = 10.2 - 然后 c * ceiling(n/5) = 11c > cn/5 所以我们需要添加一个额外的 c。
2. 9cn/10 = (10-1)cn/10 = 10cn/10 - cn/10 = cn - cn/10 ... = cn + (-cn/10 ...)