n + 2k-3比較でサイズ（2^k +1）の配列で3番目に大きい要素を見つける

Question

"n + 2k-3の比較でサイズの配列（2^k +1） "

これは、私がすべてのポイントを得られなかったAlgorithmsコースの最終試験にあった質問でした。私は徹底的なインターネット検索の後に正解が何であるか分かりません。

私はそれが2番目に大きい同じ問題の拡張バージョンだが、要求されたタイトな比較境界が難しいとの疑問に思った。 私はK番目の要素hereを見つけるために数学的な説明を見つけましたが、それは私が理解するにはあまりにも複雑でした。私たちは、トーナメントツリーを使用します

：

が試験自体では、配列のサイズからn = 2^kの+ 1

を示して私の答えは、このようなものでした。まず、任意の要素を除外します。
次に、2^k要素からなるツリーを構築します。したがって、ツリーにはK個のレベルがあります（log（2^k））。

優勝者を見つけると、n-2の比較が必要になります。

勝者に負けた人の中で最大の要素を見つけます。 （K-1 comp。）

ファイナルの敗者に負けた人の中で最大の要素を見つける。 （K-2 comp。）

ここでは、最初に除外したものと比較します。 （2件）

3番目のうち最大のものが3番目に大きい配列です。

合計比較：N - 2 + K - 1 + K - 2 + 2 = N + 2K - 3

私は2つのミスをやった25

のうち10ポイントを得ました。主なものは、希望の要素が勝者のサブツリーにある場合、私の答えは間違っています。また、正解は最後に比較した3の2番目に大きいと思われます。次のように私が見つけ

別のアルゴリズムは、次のとおり
トーナメントツリーを-Building、勝者を求める（N - 2）勝者にすべての敗者を比較して第二最大の-Finding
。 （k - 1）
- 答えは、2番目に大きい敗者の中で最大のものであり、1番目の木で決勝で失われたものの敗者です。 （log（k + 1）+ K-1-1）

- このソリューションでは、除外した要素が配列内で最大ではないと仮定しています。もしそうなら、私はそれがどのように機能するのか分かりません。 また、私はたぶん比較の数を正しく理解していなかったでしょう。

より良い説明アルゴリズムがあるかどうかはわかります。 L番目の（Kが撮影された..）のための一般化されたものがもっとあるかどうかを知りたいと思っています。要素の2 = 1 ^K、任意に選択された - 予め

おかげで、

イタイ

Answer 1

1. はNでトーナメントツリーを構築します。 （n - 2回の比較）

2. リーフでは、選択されていない要素で選択した要素の最大値を置き換えます。トーナメントツリーを再構築します。 （k比較）

3. 2番目に大きいアルゴリズムのように、新しい最大値まで失われた要素の最大値をとります。 （k - 1回の比較）

練習問題として正解証明を残します。