1

これは宿題だったのですが、講師が解法を説明する講義を見逃してしまい、いまだに解けません...

区間 [0,1] (つまり、x1、x2、x3、...、xn) に n 個の実数が与えられた場合、これらの n 個の数の順列を与える最悪の場合の線形時間で実行されるアルゴリズムがあることを示します。隣接する数の差の合計が 2 未満になるようにします。与えられたヒントは「バケツ」でした。

4

3 に答える 3

2

さて、あなたはこのように行くことができます。セグメント[0, 1]に分割： 、、...、。k[0, 1/k)[1/k, 2/k)[(k-1)/k, 1]

ここで、リストを調べて、最初に2番目のセグメントに収まる番号よりも、最初のセグメントに収まるすべての番号を新しいリストに入れます。これは1回のパスで実行できますO(n)。

今必要な金額を考えてみましょう。同じセグメント内の数の差は、せいぜい1/k、そのような差の数ですn-(k-1)。残りの(n-1)差分は、隣接するバケットの数値の間にあり、全体で（それは明らかですが、なぜですか？）以下1です。合計はによって制限され(n-k+1)/k + (k-1)/kます。十分に小さい場合は十分にk大きい場合に作成できます。

詳細：

違いを2色に塗りましょう。同じセグメントの数字の違いは青で塗りつぶされ、異なるセグメントの数字の違いは赤で塗りつぶされます。順序付けのおかげで、最初は1番目のセグメントの番号（おそらく0）のみがあり、2番目のセグメントの番号はありません。したがって、最初にいくつかの青の違い、赤の違い、さらにいくつかの青の違い、再び赤の違いなどがあります。

赤の違いの数を見てみましょう。k-1明らかに赤の違い以上のものはありませんよね？それぞれの赤い違いが1つのセグメントからより高いセグメントにジャンプするからです。残りの違いは青です。

1/k被減数と減数は同じセグメントからのものであるため、ここで、それぞれの青の差は、以下です。そして、すべての赤い違い（つまり、それらの合計！）は1を超えません。（これは宿題の質問なので、残りはスキップします。）

訂正：
すべての赤の差の合計は2-2/kを超えません。何故ですか？さて、見てみましょう。最初の赤い違いは、最悪の場合、あるセグメントの開始からA他のセグメントの終了までである可能性がありますB。2つ目は、最悪の場合、他のセグメントの最初から最後までです。したがって、差の合計では、最初と最後を除くすべてのセグメントが最大2回カウントされます。BC

于 2012-04-12T13:27:08.857 に答える
0

インターバルを n 個の等しい長さのインターバルに分割してみてください。ここで、数値が属する区間に数値を任意の順序で配置し、これが問題を解決することを証明します。

于 2012-04-12T13:23:46.010 に答える
-1

バケットの並べ替えについて学習しましたか? http://en.wikipedia.org/wiki/Bucket_sort

ソートされた配列の動作も見てください: { 0, .5, .75, 1 } : 差の合計は 1 です。

それをソートされていない配列の動作と比較してください: { .75, .5, 0, 1 } : 差の合計は 1.75 です

于 2012-04-12T13:24:03.573 に答える