問題タブ [median-of-medians]

個人的には、中央値の中央値は本当の中央値ではないと思います。正しい？
したがって、上記のステートメントが当てはまる場合、中央値の中央値をピボットとして使用して配列を分割し、K 番目の最小要素の時間計算量の最悪のケースが O(n) になるのはなぜですか? 「n」は要素の数です。

この質問はこれまでに何百万回も出されていることは承知していますが、これが少し異なり、もう少し興味深いものになることを願っています。Dor と Zwick の論文に出くわしました。これは、<= 3n の比較で n 個の整数の配列の中央値を見つけることができるというものです。論文はこちら: http://eccc.hpi-web.de/report/1995/031/download

誰かが実際にこれを実装したことがありますか? これは非常に複雑に思えます。実行して、より標準的なバージョンのアルゴリズムと比較するのを楽しみにしています。

Medians of Medians を使用して nth_number 選択アルゴリズムを実装しました。ウィキペディアでは、空間の複雑さは O( 1 ) であると述べています

これらの中央値の中から中央値を見つけるために、一時的な配列に中央値を格納する必要がありました。余分なメモリを使用せずにそれを行うにはどうすればよいでしょうか? スペースの複雑さを増加させるとは見なされない場合は、説明してください。

線形選択 (中央値アルゴリズムの中央値) の再帰方程式は次のとおりであることを知っています。

しかし、これらの用語はどこから来たのでしょうか? 私は理解しようとしてきましたが、私は非常に混乱しています。誰でも光を当てることができますか？

私は compsci の学生で、Analysis & Design II のクラスで次の問題を受けました。

順序付けられていないセットの中央値は、同点がないと仮定して、中央値よりも少ない要素の数が、より多い要素の数の 1 つの範囲内にあるような要素です。

(a) 3 つの異なる値 a、b、c の中央値を見つけるアルゴリズムを書きます。

(b) アルゴリズムが平均的なケースと最悪のケースで行う比較の回数を決定します。

私が検索して学んだことから、これは、ソートされていない配列の k 番目の要素を見つけること、または中央値の中央値を見つけることと呼ばれているようです。

しかし、私たちはまだクイックソートを学んでいません。とはいえ、この問題で提示されている定義を完全に理解しているとは言えません。また、3つの異なる値a、b、cの中央値を見つけることは、サイズ3のセットの中央値を見つけることを意味しますか?

私は必ずしも答えを探しているわけではありません。簡単な説明や説明だけです。ありがとう。

試み #1

(a) templatetypedef のアドバイスに従って、これを解決するための単純なアルゴリズムを考え出しました。

非常にナイーブで醜いことは承知していますが、より良い解決策を思いつくことができず、すでに時間がかかりすぎています。

(b) c < a < b で比較が 2 回の場合が最良のケースで、比較が 9 回で a < c < b の場合が最悪のケースのようです。では、平均は (2+9)/2 で、5 回または 6 回の比較になりますか?

それとも私は今ナイーブですか？

試み #2

(a) では、thang のアドバイスに従って、比較の数を 3 に最小限に抑えるために一生懸命努力しました。数学的に言えば、あなたの言いたいことは理解できます。残りの州をチェックa<b, b<c, a<cして差し引くだけで十分ですが、コード化する方法が見つかりませんでした...これが私の最善の試みです:

これよりもうまくやる方法がわかりません：

(b) 最良のケース: 1 回の比較。平均的なケース: 5/2 = 2 ～ 3 回の比較。最悪の場合: 5 回の比較。

もっといい？

最終的解決

おかげさまで、苦労してようやく手に入れることができました。私の最後のアルゴリズムは正しいのですが、カウントが間違っていました。

(b) 最良のケース: 2 つの比較。平均的なケース: 2 つの比較。最悪の場合: 3 回の比較。

セットアップ: さまざまな年に建てられた多数の建物のエネルギー使用データがあります。Tableau で作成された日付別のエネルギー使用量を分析したいと考えています。私が最初に抱えた問題は、サンプルに含まれる建物の数が、各年の堅牢なセットを作成するのに十分でなく、結果の出力が大量のノイズを示していることでした。多数の高い外れ値がありますが、0 に近い外れ値はないため、分布は右に歪んでいます。そのため、中央値を使用して少数の (そしておそらく誤った) 高い外れ値の影響を減らしたいと考えています。

望ましい解決策: 5 年間の「移動」または「移動」中央値を作成します。これには、指定された年のいずれかの方向の 2 年以内のすべての建物が含まれ、各セットがその年に集中するようになります。

Tableau で試したこと: WINDOW_MEDIAN([ENERGY],-2,2) を使いたかったのですが、集計関数です。そこで、WINDOW_MEDIAN(MEDIAN([ENERGY],-2,2) を試してみました。残念ながら、これにより 5 つの中央値の中央値が得られます (中央値の中央値?! ブー!)。各 5 年のウィンドウで表されるすべての個別の建物 (集約された中央値ではない)。

これを行う方法について何か考えはありますか？ありがとう！

以下は、中央値アルゴリズムの中央値を理解しようとする私のコードです (サイズ 5 のブロックを使用)。入力の中央値を取得する方法は理解していますが、中央値が得られるまで入力を繰り返し続けるようにブロックをコーディングする方法がわかりません。次に、その中央値を取得した後、それをピボットとして使用して、役に立たない情報を捨てて入力を分割する方法がわかりません。getMediansArrayサイズ ceil(input.length/5) の配列を返し、配列getMediansから中央値を返します (長さ <= 5 の配列でのみ使用されます)。

Median of Medians ピボット メソッドを使用して select-kth アルゴリズムを実装しています。具体的には、ここにリストされている疑似コードに従っています。. しかし、コードがクラッシュします (以下で説明するエラー)。クラッシュする理由はわかりますが、それに対して何ができるかわかりません。

エラー

理由
wiki リンクでは、メソッドは の場合に値selectを返します。ただし、相互再帰が の return ステートメントから呼び出される場合、それは (インデックスではなく) 値を親に返し、親はその値を として設定することを意味します。 left == rightpivotpivotIndex

コード

コードが機能しない理由は完全に理解していますが、アルゴリズムが正確に指定しているように見えるため、修正方法がわかりません。ポインタは大歓迎です！