クイックセレクト時間の複雑度

Question

クイックセレクトアルゴリズムの平均比較回数を計算します。私は平均ランタイムがO（n）であることを知っていますが、定数も知る必要があります。答えを見つけるためにネットサーフィンをしてください。しかし、私は別の解決策を読むと混乱します。 それは4nですか？ 3n？または何？ 誰でも助けてくれますか？ ありがとうございます

Answer 1

これはO(n)です。関心のある定数はパーティションの仕方によって異なります。これは、ピボットごとに異なります。だからこそ、それはcnです。ここで、cは一定です。 （それは4または3または5などとすることができる）。

最悪の場合O(n^2)平均ケースO(n)になる可能性があります。それは確かにあなたが言うことができるすべてです。