3

ソートされていない配列データ構造でアイテムを見つけるための平均ステップ数がN/2である理由を誰かが説明できますか？

4

5 に答える 5

3

これは、配列内の数値について何を知っているかに大きく依存します。すべての確率質量が単一の値にある分布からそれらがすべて引き出された場合、たとえば、すべての値が同じであるため、探している値を見つけるのにちょうど 1 ステップかかります。

ここで、配列が個別の値のランダムな順列で満たされているというかなり強い仮定を立てましょう。これは、任意の並べ替えられた個別の要素のリストを選択し、それをランダムに並べ替えるものと考えることができます。この場合、実際に存在する配列内の要素を検索しているとします (要素が存在しない場合、この証明は失敗します)。次に、実行する必要があるステップの数は X で与えられます。ここで、X は配列内の要素の位置です。平均ステップ数は E[X] であり、次の式で与えられます。

E[X] = 1 Pr[X = 1] + 2 Pr[X = 2] + ... + n Pr[X = n]

すべての要素がランダムな順列から引き出されると仮定しているので、

Pr[X = 1] = Pr[X = 2] = ... = Pr[X = n] = 1/n

したがって、この式は次のように与えられます。

E[X] = sum (i = 1 to n) i / n = (1 / n) sum (i = 1 to n) i = (1 / n) (n)(n + 1) / 2
     = (n + 1) / 2

これは、あなたが探している答えだと思います。

于 2011-01-15T20:23:15.730 に答える
1

述べられている質問は間違っています。線形検索の方がパフォーマンスが向上する場合があります。

于 2011-01-15T20:19:35.713 に答える
1

私は templatetypedef が最も有益な答えを持っていると思いますが、この場合はもっと単純な答えがあります。

セット {x1, x2, ..., xn} の順列を考えます。ここで、n = 2m です。次に、見つけたい要素 xi をいくつか取ります。xi がインデックス m - k で発生する各順列には、xi がインデックス m + k で発生する対応する鏡像順列があります。これらの可能なインデックスの平均は、ちょうど [(m - k) + (m + k)]/2 = m = n/2 です。したがって、セットのすべての可能な順列の平均は n/2 です。

于 2011-01-16T22:02:01.197 に答える
1

おそらく、平均が N/2 である理由を示す簡単な例は次のとおりです。

ソートされていない 10 個の項目の配列があるとします: [5, 0, 9, 8, 1, 2, 7, 3, 4, 6]. これはすべての数字[0..9]です。

配列はソートされていない (つまり、項目の順序について何も知らない) ため、配列内の特定の項目を見つける唯一の方法は線形検索を行うことです。探しているか、最後に到達します。

それでは、各アイテムを見つけるのに必要な操作の数を数えてみましょう。最初の項目 (5) を見つけるのに必要な操作は 1 回だけです。2 番目の項目 (0) を見つけるには 2 つかかります。最後の項目 (6) を見つけるには、10 回の操作が必要です。10 個の項目すべてを見つけるために必要な操作の総数は、1+2+3+4+5+6+7+8+9+10、つまり 55 回です。平均は 55/10、つまり 5.5 回です。

「線形検索は、平均して N/2 ステップかかります」という従来の通念では、多くの仮定が立てられています。最大の 2 つは次のとおりです。

  1. 探しているアイテムは配列にあります。項目が配列にない場合、それを判断するには N ステップが必要です。そのため、存在しないアイテムを頻繁に探している場合、検索ごとの平均ステップ数は N/2 よりもはるかに多くなります。

  2. 平均して、各アイテムは他のアイテムとほぼ同じ頻度で検索されます。つまり、「0」を検索するのと同じくらい頻繁に「6」を検索します。あるアイテムが他のアイテムよりもはるかに頻繁に検索される場合、検索ごとの平均ステップ数は、より頻繁に検索されるアイテム。最も頻繁に検索される項目の位置に応じて、この数は N/2 よりも大きくなったり小さくなったりします。

于 2011-01-15T21:29:04.323 に答える
0

質問の簡単な再定式化を考えてみましょう:

どれくらいが限界だろう

lim (i->inf) of (sum(from 1 to i of random(n)) /i)

またはCで：

int sum = 0, i;
for (i = 0; i < LARGE_NUM; i++) sum += random(n);
sum /= LARGE_NUM;

値が均等に分布していると仮定すると( ～randomの各値が生成される可能性は等しい)、期待される結果は になります。1n(1+n)/2

于 2011-01-15T20:24:57.787 に答える