7

線形時間 O(n) でサイズ n の配列の k 番目に小さい (または最大の) 要素を見つけるために、順序統計を読みました。

中央値の中央値を見つけるために必要な 1 つのステップがあります。

  1. 配列を [n/5] の部分に分割します。各パーツには 5 つの要素があります。
  2. 各部分の中央値を見つけます。(現在 [n/5] 個の番号があります)
  3. 最後の数字だけになるまで、手順 1 と 2 を繰り返します。(つまり、再帰的)

T(n) = T(n/5) + O(n) となり、T(n) = O(n) を得ることができます。

しかし、最終的に得られる数値は、中央値の中央値ではなく、大きな配列がある場合、中央値の中央値の中央値の中央値の中央値の中央値の中央値の中央値の中央値です。

125 要素の配列を考えてみてください。

まず、それを 25 の部分に分割し、25 の中央値を見つけます。次に、これらの 25 の数値を 5 つの部分に分割し、5 つの中央値を見つけます。最終的に、中央値の中央値の中央値である数値を取得します。(中央値の中央値ではありません)

私が気にする理由は、中央値の中央値よりも小さい（または大きい）要素が最大で約[3/4] * n個あることがわかるからです。しかし、それが中央値の中央値ではなく、中央値の中央値の中央値である場合はどうなりますか? 最悪の場合、ピボットよりも小さい (または大きい) 要素が少なくなる必要があります。これは、ピボットが配列の境界に近いことを意味します。

非常に大きな配列があり、その中央値の中央値の中央値の中央値の中央値の中央値の中央値を見つけた場合。最悪の場合、見つかったピボットがまだ境界に非常に近い可能性があります。この場合、時間計算量はどのくらいですか?

125 要素のデータセットを作成しました。結果は9ですか？

0.8 0.9 1 inf inf
1.8 1.9 2 inf inf
6.8 6.9 7 inf inf
inf inf inf inf inf
inf inf inf inf inf

2.8 2.9 3 inf inf
3.8 3.9 4 inf inf
7.8 7.9 8 inf inf
inf inf inf inf inf
inf inf inf inf inf

4.8 4.9 5 inf inf
5.8 5.9 6 inf inf
8.8 8.9 9 inf inf
inf inf inf inf inf
inf inf inf inf inf

inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf

inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf
inf inf inf inf inf

ここで、inf は数値が十分に大きいことを意味します。

4

1 に答える 1

3

... の中央値の中央値の中央値を [median of]* = Mとして示しましょう。

まず、中央値アルゴリズムの中央値 (適切なピボットを選択するため) は再帰的ではないと考えています。アルゴリズムは次のようになります。

  1. 要素を 5 つのグループに分割します
  2. 各グループの中央値を求める
  3. 中央値の中央値を見つけて、ピボットとして使用します。

中央値の中央値は、3n/4 ではなく、3n/10 要素よりも小さく、別の 3n/10 要素よりも大きくなります。中央値を選択した後、n/5 の数値があります。中央値の中央値は、n/10 であるこれらの数値の半分よりも大きい/小さいです。これらの各数値はそれ自体が中央値であるため、2 つの数値よりも大きい/小さいので、別の 2n/10 の数値が得られます。合計すると、n/10 + 2n/10 = 3n/10 の数値が得られます。

2 番目の質問に答えるために、例のデータセットで 5 のグループを収集し、それらの中央値を計算した後、次のシーケンスが得られます。

1, 2, 7, inf, inf
3, 4, 8, inf, inf
5, 6, 9, inf, inf, 
inf, inf, inf, inf, inf, 
inf, inf, inf, inf, inf.

したがって、中央値の中央値は実際には 9 になります。

提案された [median of]* アルゴリズムの実行時間は次のようになります。

T(n) = O(n * log(n))

次に、 Mより小さい/大きい数値がいくつあるのかを分析してみましょう。次のグループがあります。

  • 深さ 1: n/5 要素すべての中央値
  • 深さ 2: n/25 要素すべての中央値
  • ...
  • 深さ i: n/(5^i) 要素 すべての中央値

各グループは、前の深さの 2 要素より少ない/大きい、つまり前の深さの 2 要素より少ない/大きい、などです。

合計で計算すると、Mが (n * (2^k) + k * n) /((2^k) * (5^k)) より大きい/小さいことがわかります。深さ = 1 の場合、3n/10 である中央値の中央値が得られます。

深度が [log_5 (n)]、つまり n = 5^k であると仮定すると、次のようになります。

5^k * (k + 2^k)/(5^k * 2^k) -> 1.

于 2013-07-10T23:43:44.703 に答える