問11.7

[Maruoka842]

相異なる要素 n 個の要素をクイックソートするときの比較回数の期待値が 2nH(n)-n+H(n) になるという主張に疑問を持っています。

書籍では n=1 のとき 3 だが、長さ 1 だから実際は 0 回の比較で終わるので矛盾。
書籍では n=2 のとき 11/2 だが、0 と 1 のいずれのピボットを選んでも 2回の比較で終わるので矛盾。

以下、Twitter で友達とやり取りした私が正しいと思っている期待値の導出です。
https://twitter.com/___n___z/status/1301563220121985025

要素 a と b (a<b) が 比較される確率は 2/(b-a+1) 。
d=b-a+1 毎に和を取ると Σ[d=2..n] (2/d)(n-d+1) = 2(n+1)H(n)-4n。

要素 a がピボット a と比較される確率は a ∈ {0, n-1} のとき 1/2 、そうでないとき 2/3。和は (2/3)n-1/3。

答えは
n>2 のとき 2(n+1)H(n)-4n+(2/3)n-1/3=2(n+1)H(n)-(10/3)n-1/3
n=1 のとき 0

[spinute]

↑が正しい気がします！