リストの最小数を見つける簡単な方法は、単純にn回の比較であり、2番目に小さい数が必要な場合は、もう一度調べるか、最初の反復中に別の変数を追跡することができます。いずれにせよ、これは両方の数値を見つけるために2nの比較を必要とします。
したがって、n個の異なる要素のリストがあり、最小のものと2番目に小さいものを見つけたいと仮定します。はい、最適なアルゴリズムは最大でn + Chief（lg n）-2回の比較を行います。（ただし、最適な方法には興味がありません）
しかし、2nの比較を行う簡単なアルゴリズムを使用せざるを得ないとします。最悪の場合、2n回の比較が必要になります。しかし、平均はどうですか？簡単なブルートフォースアルゴリズムを使用して最小と2番目に小さいものを見つけるのにかかる平均比較数はいくつですか？
編集：それは2nより小さくなければならないでしょう-（以下の私のコメントからコピーして貼り付けました）私は2番目に小さいものを追跡しているtmp2変数と私がいるインデックスを比較します。現在のインデックスの値がtmp2より小さい場合を除いて、最小値を追跡しながらtmp1変数と再度比較する必要はありません。したがって、比較の数を2nから減らすことができます。それでもn以上かかるでしょう。はい、最悪の場合、これでも2nの比較が必要になります。しかし、平均してすべてがランダムに入れられた場合...
n +何かの比較になると思いますが、2番目の部分がわかりません。どういうわけかlognを巻き込む方法があると思いますが、それを証明する方法について何かアイデアはありますか？
（同僚が昼食時にこれを私に尋ねました、そして私は困惑しました。申し訳ありません）もう一度、それはちょっと一般的な知識なので、私は最適なアルゴリズムに興味がありません。