サイズ N の配列の場合、必要な比較の回数はいくつですか?
ベストアンサー1
最適なアルゴリズムでは、n+log n-2 回の比較を使用します。要素を競争相手と考え、トーナメントで順位付けを行います。
まず、ツリー内の要素を比較します
|
/ \
| |
/ \ / \
x x x x
これには n-1 回の比較が必要で、各要素は最大 log n 回の比較に関係します。最大の要素が勝者となります。
2 番目に大きい要素は、勝者との試合に負けているはずです (別の要素との試合に負けることはできません)。そのため、勝者が対戦した log n 個の要素の 1 つになります。log n - 1 の比較を使用して、それらの要素を見つけることができます。
最適性は敵対的議論によって証明される。https://math.stackexchange.com/questions/1601またはhttp://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdfまたはhttp://www.imada.sdu.dk/~jbj/DM19/lb06.pdfまたはhttps://www.utdallas.edu/~chandra/documents/6363/lbd.pdf