haskell-jp / random #94 at 2021-11-08 12:30:37 +0900

Haskell Day 2021 お疲れさまでした。私の発表 take k (sort xs) in Haskell has O(n + k log k) time complexity の間にクイックソートと遅延評価が組み合わさったときの計算量がどうなるかというコメントが @as_capabl さんからあったと思うので、この場を借りて回答します。（チャットで書いたつもりが、リンクを含んでいたせいかアーカイブに残っていなかったもので……）
結論としては、クイックソートの場合も実装が適切であれば take k (sort xs) の平均時間計算量を O(n + k log k) にできそうです。詳細な説明は Heinrich Apfelmus の投稿 や Peter Van Roy の講義動画 にありますが、いずれの場合も「平均時間計算量を考えているので、partition はリストを大体同じ長さの2つの部分に分割するものと考える」というクイックソートの平均時間計算量の証明でありがちなごまかし（だと自分は思っているんですが、これって妥当なんでしょうか？）が見られるので、証明をより精緻にする余地があると思います。

Peter Van Roy の講義動画は今年のも上がってました。もしかしたら、こっちの方が分かりやすいかもしれません。 https://youtu.be/4-u64wT3Jxk

もうしばらく考えて、スライド内でも最初の方に引用していた [Paredes and Navarro 2006] と全く同じ議論で lazy quicksort に関して同様の結論が導けるような気がしました（が実はこれも p.1 しか読んでいない）。時間があればもう少し読んで考えてみます。 https://doi.org/10.1137/1.9781611972863.16

なるほど、ありがとうございます。「`take k` が手前のリストで足りれば後ろのリストは触らないから……」くらいの雑な推測でしたが、きちんとやれば面白いテーマのようですね