algorithm - SELECT算法分析中的递归

Question

在 CLRS中，对查找数组中第 i 个最小元素(2/e, page 191, section 9.3)的算法的分析通过以下归纳证明给出：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/10to得到的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 ...)

Answer 2

只是为了为第 2 行添加更多信息。我们有ceiling(x) <= x + 1。因为 x 舍入到下一个整数。假设m <= x < m+1，那么ceiling(x) = m+1,x+1 >= m+1，所以我们有ceiling(x) <= x + 1。在那种情况下，c * ceiling(n/5)必须小于或等于c*(n/5+1)，然后你得到了额外的c。