2012-02-28 22 views
52

私は、次の例のアルゴリズム「中央値の中央値を」理解したい:理解「中央値の中央値」アルゴリズム

私たちは5つの要素それぞれに9グループに分かれて45個の異なる数字を持っています。

48 43 38 33 28 23 18 13 8 

49 44 39 34 29 24 19 14 9 

50 45 40 35 30 25 20 15 10 

51 46 41 36 31 26 21 16 53 

52 47 42 37 32 27 22 17 54 
  1. 最初のステップは、再帰的に
  2. (この場合には、彼らがすでにソートされている)第2工程をグループごとにソートされ、セットすなわちFiのND中央値の「真」の中央値(50 45 40 35 30 25 20 15 10が)になりますこれらの2つのグループ

    30 10 
    
    35 15 
    
    40 20 
    
    45 25 
    
    50 
    
  3. をソート

    50 25 
    
    45 20 
    
    40 15 
    
    35 10 
    
    30 
    

    :2グループに分け

中央値40及び15である(場合に数字も、我々は左中央値を取ったれる) ので、戻り値は中央値の15が「真」の中央値(50 45 40 35 30 25 20 15 10)が30である。さらに、5つの要素未満であります15は、wikipedia

に記載されている45の30%よりもはるかに小さいので、T(n) <= T(n/5) + T(7n/10) + O(n)は失敗します。 Wikipediaの例ではところで

、私は36のように再帰の結果を得る真の中央値は、だから、47

あるしかし、私はいくつかのケースでは、この再帰は中央値の真の中央値を返さないかもしれないと思います。私は間違いがどこにあるのか理解したい。

+3

@kaoD:サイトのコミュニティポリシーでは、「問題は宿題です」と認めます。参照:http://meta.stackexchange。@kaoD:宿題に関する質問を投稿するのに本質的に間違ってはいませんが、ほとんどのメンバーがその質問にどのように答えているかに影響します。com/a/10812 – Orbling

+4

したがって、そのように述べるべきであり、どのような進展が示されているのか。答えは、通常、解決するのではなく、指導しようとする試みです。 – Orbling

+13

@Orblingは関連性がありますか?この質問の背後にある理由が何であれ、smnvhn(他者と同様)は良い答えから学ぶことができます。私は、すでにsmnvhnがすでにこれにいくつかの考えを置いていることを示している。このように、これが本当に宿題であると判明した場合、ポスターは投稿された発言や回答によってより多くのことを学ぶでしょう。 – Joris

答えて

34

問題は、中央値の真の中央値を求める段階にあります。あなたの例では、これらの中央値を持っていた:

50 45 40 35 30 25 20 15 10 

このデータセットの真の中央値は30、いない15です。あなたは5のブロックにグループを分割し、それらの中央値を取ることによって、この中央値を見つけることができません。代わりに、この小さなグループで選択アルゴリズムを再帰的に呼び出すことによって行われます。あなたのロジックの誤差は、このグループの中央値は、各ブロックの中央値を求める2つのブロック

50 45 40 35 30 

25 20 15 10 

に上記シーケンスを分割することによって発見されると仮定されます。代わりに、メジアン・オブ・メジアンアルゴリズムは、完全なデータセット50 45 40 35 30 25 20 15 10で再帰的に自身を呼び出します。内部的には、このグループを5つのブロックに分割してソートするなどしますが、パーティション化ステップのパーティションポイントを決定するために行います。このパーティション化ステップでは、再帰呼び出しでメジアンの真の中央値が見つかりますこの場合は30になります。元のアルゴリズムの分割ステップとして30を中央値として使用する場合は、実際には必要に応じて非常に良好な分割を取得します。

希望すると便利です。

+0

ありがとう、それは私の間違いでした! – simon

+7

私はsmnvhnのエラーと "5つのブロックへの内部分割"の違いを教えてくれる部分から理解できませんでした。それらはどう違いますか?あなたは彼のエラーを説明した後、smnvhnの例を続けることができますか?私が理解していることは、新しい配列の再帰の後、配列はsmnvhnが言うように5つのグループに分割され、次の再帰で再び[40,15]を渡すので、再び15が返されるということです。 –

+2

また、この例では、配列が既にソートされているため、パーティションを見つけることは役に立たないので、選択した9つの要素のうち、配列は変更されません。 –

24

中央値のアルゴリズムの中央値はpseudocodeです(ご使用の例に合わせて少し変更)。ウィキペディアの擬似コードは、selectIdx関数呼び出しの内部動作を記述することができません。

説明のためにコードにコメントを追加しました。

// L is the array on which median of medians needs to be found. 
// k is the expected median position. E.g. first select call might look like: 
// select (array, N/2), where 'array' is an array of numbers of length N 

select(L,k) 
{ 

    if (L has 5 or fewer elements) { 
     sort L 
     return the element in the kth position 
    } 

    partition L into subsets S[i] of five elements each 
     (there will be n/5 subsets total). 

    for (i = 1 to n/5) do 
     x[i] = select(S[i],3) 

    M = select({x[i]}, n/10) 

    // The code to follow ensures that even if M turns out to be the 
    // smallest/largest value in the array, we'll get the kth smallest 
    // element in the array 

    // Partition array into three groups based on their value as 
    // compared to median M 

    partition L into L1<M, L2=M, L3>M 

    // Compare the expected median position k with length of first array L1 
    // Run recursive select over the array L1 if k is less than length 
    // of array L1 
    if (k <= length(L1)) 
     return select(L1,k) 

    // Check if k falls in L3 array. Recurse accordingly 
    else if (k > length(L1)+length(L2)) 
     return select(L3,k-length(L1)-length(L2)) 

    // Simply return M since k falls in L2 
    else return M 

} 

あなたの例を考える:

を中央値関数の中央値(k = 45/2 = 22有する)のような45個の要素のアレイ全体にわたって呼び出される:初めてM = select({x[i]}, n/10)

median = select({48 49 50 51 52 43 44 45 46 47 38 39 40 41 42 33 34 35 36 37 28 29 30 31 32 23 24 25 26 27 18 19 20 21 22 13 14 15 16 17 8 9 10 53 54}, 45/2) 
  1. 配列{x[i]}には、次の番号が含まれます。50 45 40 35 30 20 15 1040 20をこのコール、n = 45、ひいては選択関数呼び出しで アレイ{x[i]}は、次の数値が含まれます、M = select({50 45 40 35 30 20 15 10}, 4)

  2. 二度目M = select({x[i]}, n/10)が呼び出されるであろう。 この呼び出しでは、n = 9となるため、呼び出しはM = select({40 20}, 0)になります。 この選択コールは、戻り値M = 20を割り当てます。

    疑問に思ったところで、今度はをM = 20の周りに、k = 4で区切ります。

    Lの配列は、50 45 40 35 30 20 15 10です。

    アレイは規則L1 < ML2 = ML3 > Mに従ってL1, L2L3に分割されます。したがって:
    L1: 10 15
    L2: 20
    L3: 30 35 40 45 50

    k = 4ので、それはlength(L1) + length(L2) = 3よりも大きいです。そのため、検索は現在、以下の再帰呼び出しを継続されます。
    return select(L3,k-length(L1)-length(L2))

    に換算さ:結果として30を返します
    return select({30 35 40 45 50}, 1)

    。 (Lは5以下の要素を持つので、k番目の要素、つまりソートされた配列の1番目の位置は30です)。

次に、M = 30は45個の素子のアレイ全体にわたって最初select関数呼び出しで受信され、アレイLを分離同じ分割ロジックは約M = 30最終的に中央値の中央値を得るために適用されます。

Phew!メジアンアルゴリズムのメジアンを説明するのに十分冗長で明確であることを願っています。

+2

私はこの回答が少なくとも投票に値すると思う。 –

+1

中央値計算の中央値を探して、このスレッドを見つけました。私はJavaで擬似コードを再構築しようとしましたが、選択の2番目の呼び出しで配列の長さのために例外が発生しました...誰かがx [i]と{x [i]}の意味を説明できますか?どのサイズにする必要がありますか?ありがとうございました! –

+1

変数がすべて1文字であるため、コードをさらに難しくしています。 –