在 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系数哪里去了?
这不是作业
谢谢!
最佳答案
- 额外的
c
来自c*celing(n/5)
- 考虑n/5 = 10.2
- 然后c * ceiling(n/5) = 11c > cn/5
所以我们需要添加一个额外的c
。 9cn/10 = (10-1)cn/10 = 10cn/10 - cn/10 = cn - cn/10 ... = cn + (-cn/10 ...)
关于algorithm - SELECT算法分析中的复现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12850008/