最低限必要な比較数

Question

4つの異なる要素から最大の要素を見つけるために必要な最小限の比較数は何ですか？私は5つの異なる数字のためにそれが6、床（5/2）* 3であることを知っています。これはclrsの本からです。私はこれを見つけるための一般的な公式はない、あるいはそこにいるのは知っていますか？

編集明確化

これら4つの要素は、あなたが要素を横断する最大の要素を追跡するためにカウンティング技術に興味を持っていないイム（これら4つの要素の全ての順列のための）任意の異なる順序で可能性があり、 >または<のような比較があります。

Answer 1

（4要素分）比較数は3です。

通常、Nの要素のうち最大のものを見つけるには、N-1の比較が必要です。 、ちょうど最初の二つを比較して、より大きなを選択し、次の1と比較：

1. N-1の比較と解決策が常にある：これはあなたの5つの数字ではなく、6

   証明のために4を与えます大きいものを選択して次のものと比較してください....

2. この解決策はすべての要素を比較しないため、解決策が短くなることはありません。

QED。

Answer 2

これを競争と考えてください。 2つの要素を比較することで、より緩やかなものと勝者が得られます。

したがって、nの要素があり、1つの最終的な勝者が必要な場合は、他の要素を除外するにはn-1の比較が必要です。

要素、B、C、Dのための

Answer 3

は> B + C + Dあれば、それは唯一最大であることを知るために1回の比較が必要。

あなたは幸運なことをする必要があります。

Answer 4

元の質問には答えられないが、the minimum number of comparisons needed to find the smallest AND the largest number from an unsorted array（証明付き）のこの直感的ではない投稿を読んで楽しんでいた。