0

在此处输入图像描述

在快速排序分析中的上述关系（由 sedgewick 算法 4 提供）中，分区成本为 N+1 。有人可以解释一下吗？这是否意味着 N+1 比较？

（我在stackexchange中尝试了类似的问题，但无济于事）

4

1 回答 1

0

是的，平均而言，分区需要 n+1 次比较。（实际上是n+1-(1/n)）

http://users.encs.concordia.ca/~chvatal/notes/qs.pdf

于 2013-07-20T07:38:10.690 回答