algorithm - 「中央値の中央値」アルゴリズムを理解する

Question

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

それぞれ 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

最初のステップは、すべてのグループを並べ替えることです (この場合、それらは既に並べ替えられています)
2 番目のステップでは、中央値の「真の」中央値 ( ) を再帰的に見つけます。50 45 40 35 30 25 20 15 10つまり、セットは 2 つのグループに分割されます。
```
50 25

45 20 

40 15

35 10

30
```
これらの 2 つのグループを並べ替える
```
30 10

35 15 

40 20

45 25

50
```

中央値は 40 と 15 です (数値が偶数の場合、左中央値を取ります)。したがって、返される値は 15 ですが、中央値の「真の」中央値 ( 50 45 40 35 30 25 20 15 10) は 30 です。ウィキペディアで言及されている 45 の %

そしてT(n) <= T(n/5) + T(7n/10) + O(n)失敗します。

ちなみに、ウィキペディアの例では、再帰の結果は 36 になります。ただし、真の中央値は 47 です。

したがって、場合によっては、この再帰が真の中央値の中央値を返さない可能性があると思います。私の間違いがどこにあるかを理解したいです。

score 37 · Accepted Answer

問題は、中央値の真の中央値を見つけると言うステップにあります。あなたの例では、これらの中央値がありました：

50 45 40 35 30 25 20 15 10

このデータセットの真の中央値は 15 ではなく 30 です。この中央値は、グループを 5 つのブロックに分割してそれらの中央値の中央値を取得することによってではなく、代わりに、この小さなグループに対して選択アルゴリズムを再帰的に呼び出すことによって求められます。あなたのロジックのエラーは、このグループの中央値が上記のシーケンスを 2 つのブロックに分割することによって見つかると仮定しています

50 45 40 35 30

と

25 20 15 10

次に、各ブロックの中央値を見つけます。代わりに、median-of-medians アルゴリズムが、完全なデータセットに対して再帰的に自身を呼び出します50 45 40 35 30 25 20 15 10。内部的には、これはグループを 5 つのブロックに分割し、それらを並べ替えるなどしますが、分割ステップの分割点を決定するために行います。再帰呼び出しが中央値の真の中央値を見つけるのは、この分割ステップです。、この場合は 30 になります。元のアルゴリズムでパーティショニングステップとして中央値として 30 を使用すると、必要に応じて非常に適切な分割が得られます。

お役に立てれば！

score 36 · Accepted Answer

これは、中央値アルゴリズムの中央値の擬似コードです（例に合わせて少し変更されています）。ウィキペディアの疑似コードは、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

}

あなたの例を取る：

中央値関数の中央値は、(with k = 45/2 = 22)のように 45 要素の配列全体に対して呼び出されます。

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)

初めてM = select({x[i]}, n/10)呼び出されると、配列{x[i]}には次の番号が含まれます: 50 45 40 35 30 20 15 10. この呼び出しでn = 45は、したがって、select 関数呼び出しは次のようになります。M = select({50 45 40 35 30 20 15 10}, 4)
2 回目M = select({x[i]}, n/10)に呼び出されると、配列{x[i]}には次の番号が含まれます: 40 20. この呼び出しではn = 9、したがって、呼び出しはになりますM = select({40 20}, 0)。この select 呼び出しは値を返し、割り当てますM = 20。

さて、あなたが疑問に思った点に来て、配列LをM = 20で分割しk = 4ます。

ここで配列を覚えておいてくださいL: 50 45 40 35 30 20 15 10. 配列は、規則に従っておよびに

分割されます。したがって、であるため、より大きいです。したがって、検索は次の再帰呼び出しで続行されます。これは次のように変換されます。 L1, L2L3L1 < ML2 = ML3 > M
L1: 10 15
L2: 20
L3: 30 35 40 45 50

k = 4length(L1) + length(L2) = 3
return select(L3,k-length(L1)-length(L2))

return select({30 35 40 45 50}, 1)

結果として 30 が返されます。(L には 5 つ以下の要素があるため、k 番目、つまり並べ替えられた配列の 1 番目の位置 (30) の要素を返します)。

これで、 45 要素の配列全体に対するM = 30最初のselect関数呼び出しで受信され、配列を分離する同じ分割ロジックLがM = 30適用され、最終的に中央値の中央値が取得されます。

ふぅ！中央値アルゴリズムの中央値を説明するのに十分なほど冗長で明確であったことを願っています。

algorithm - 「中央値の中央値」アルゴリズムを理解する

2 に答える 2

Related

Reference