問題タブ [median-of-medians]

ここで c++ のアルゴリズムの実装を見つけました https://gist.github.com/andlima/1774060 しかし、数行の目的とそれらがどのように機能するかがわかりません。

1. n が特定の値を下回っている場合は配列をソートして v[k] を返すという if ステートメントを追加する必要がありますか?
2. 4 行目で、変数を 4 ずつ増やして作成するのはなぜですか? 小さな配列の量を得るには、5 で割る必要があることを理解しています。
3. 6行の「forループ」は何を担当していますか? メイン配列をより小さな配列に分割して、並べ替えてから中央値の配列を作成するためですか? なぜ swap 関数があり、なぜ if 条件と else 条件に分割するのですか?
4. 前に同じ関数行を呼び出した後に中央値配列を削除する理由
5. 25 行の for ループと 33 行のこれと 38 行のスワップの目的は何ですか?

これについて何か助けてくれて本当に本当に感謝しています。

A[1..N]整数の2 つのソート済み配列が昇順B[1..N]で提供されます。

Q: 2N 個の整数すべての中央値O(log N)-timeを求めるアルゴリズムを設計してください。N は 2 の累乗ではない場合があります。

簡単にするために、次のようO(1)に返すアルゴリズムを想定できます。m

私の問題:

1. Nのべき乗ではないかもしれませんが2、それはどういう意味ですか? （了解した）
2. 配列との両方の要素が見つかった後、入力を変更して長さを 2 のべき乗にする方法がわかりません。minmaxAB

教科書の Intro to Algorithms (CLRS) の問題 9-3 では、長さ n の配列の k 次の統計 (並べ替えた場合の配列の k 番目の要素) を見つけるための高速 O(n) アルゴリズムについて説明しています。 k が n よりもはるかに小さい場合。n が奇数の場合、このアルゴリズムの正しさについて確信が持てず、正しさを証明する方法を見たいと思っています。

基本的な考え方は、最初に配列を 2 つの半分に分割することです。1 つ目は floor(n/2) 要素、2 つ目は ceil(n/2) 要素です。次に、前半の各要素と後半の対応する要素を「組み合わせ」ます。n が奇数の場合、これは残りのパートナー化されていない要素を残します。

パートナーの各ペアについて、左のパートナーが右のパートナー以上であることを確認し、そうでない場合は 2 つを交換します。次に、後半の k 次統計量を再帰的に見つけ、前半の対応するスワップで後半に行われたすべてのスワップをミラーリングします。この後、配列全体の k 次統計量は、前半の最初の k 要素、または後半の最初の k 要素のいずれかになければなりません。

私の混乱は、配列の長さ n が奇数で、後半にパートナーのない要素が 1 つだけある場合に発生します。再帰は後半で実行され、唯一のパートナーのない最後の要素を含む、配列の最後の ceil(n/2) 要素で構成されるため、後半で行われたすべてのスワップを、対応する要素内で行われたスワップでミラーリングすることになっています。前半のパートナーは、パートナーがいないため、スワップの1つが最後の要素を含む場合に何をすべきかは不明です.

教科書では特に注意されていないようなので、最終要素が入れ替わる場合、前半は相手のミラームーブを一切行わないようにしていると思います。その結果、最後の要素は、交換した相手のパートナーを単に「盗む」だけです。ただし、この場合、アルゴリズムがまだ正しいかどうかを確認する簡単な方法はありますか? 最後の要素が他の誰かのパートナーを盗んだときに、そのパートナーが実際には k 次の統計であり、後でアクセスできない場所にスワップされた場合はどうなるでしょうか? 順序統計の選択に関係する再帰と分割のメカニズムは、私には十分に不透明であるため、自信を持ってそのシナリオを除外することはできません。

コマンド プロンプトで、指定された 500 GB ファイル内のすべての数値の中央値を見つけます。

ファイル形式例:

各行に1つの数字があります（数字は繰り返すことができます）.JAVAでこれにアプローチする方法について誰か助けてもらえますか? ファイルを分割する必要がある場合、中央値はどのように計算できますか? median に関するいくつかの投稿に出くわしましたが、そのような巨大なファイルに対する最善のアプローチを見つけることができませんでした。