1

私は問題で立ち往生していますhttp://www.codechef.com/JULY12/problems/LEBOBBLE ここでは、予想されるスワップの数を見つける必要があります。

O(n^2) ソリューションを試しましたが、タイムアウトしています。

コードは次のようになります。

swaps = 0
for(i = 0;i < n-1;i++)
    for(j = i+1;j<n;j++)
    {
        swaps += expected swap of A[i] and A[j]
    }

要素の確率はさまざまであるため、すべてのペアを比較する必要があります。したがって、私によると、上記のコード スニペットは最も効率的である必要がありますが、タイムアウトしています。

O（nlogn）で実行できますか、それともO（n ^ 2）よりも複雑です。可能であればヒントを教えてください。

4

2 に答える 2

5

よし、これについて考えてみましょう。

遅かれ早かれ、すべての数字は最終的にそれよりも小さいすべての数字と交換される必要があることを認識しています。したがって、特定の数値のスワップの総数は、それよりも小さい数値の後にある数値の総数です。ただし、これはまだO(n^2)時間です。

バブル ソートの外側のループを通過するたびに、1 つの要素が正しい位置に配置されます。一般性を失うことなく、パスごとに、残っている最大の要素がリストの最後にソートされると言います。

したがって、外側のループの最初のパスでは、最大数が最後に配置されます。これにはqスワップが必要です。ここで、qは、番号が最終ポジションから離れて開始されたポジションの数です。

したがって、このバブルソートを完了するにはq 1 +q 2 + ... +q n回のスワップが必要であると言えます。ただし、すべてのスワップで、1 つの数字が最終ポジションから 1 ポジション近くまたは 1 ポジション離れて取得されることに注意してください。私たちの特定のケースでは、数値がより大きな数値の前にあり、正しい位置またはその前にある場合、もう 1 回スワップが必要になります。ただし、数字がより大きな数字よりも後ろにあり、正しい位置よりも後ろにある場合は、必要なスワップが 1 つ少なくなります。

これが正しいことは、次の例でわかります。

   5 3 1 2 4
=> 3 5 1 2 4
=> 3 1 5 2 4
=> 3 1 2 5 4
=> 3 1 2 4 5
=> 1 3 2 4 5
=> 1 2 3 4 5 (6 swaps total)

「5」は4マス移動します。「3」は1マス移動します。「1」で2マス移動。「2」は2マス移動します。「4」は1マス移動します。合計: 10 スペース。

3 は 5 の後ろにあり、正しい位置よりも前にあることに注意してください。したがって、もう 1 つのスワップが必要になります。1 と 2 は 3 と 5 より遅れています。必要なスワップは 4 回少なくなります。4 は 5 よりも後ろにあり、正しい位置よりも後ろにあるため、必要なスワップが 1 つ少なくなります。期待値 6 が実際の値と一致することがわかります。

最初にリストをソートし、ソート中に各要素の元の位置をメモリに保持することで、 Σ qを計算できます。これはO(nlogn + n)時間内に可能です。

また、どの数字が他のどの数字よりも遅れているかを確認することもできますが、これをO(n^2)時間よりも早く行うことは不可能です。ただし、より迅速な解決策を得ることができます。

すべてのスワップは、必要な 2 つの数値を正しい位置に効果的に移動しますが、一部のスワップは実際には何もしません。前の例の最初のスワップしたがって、"3" と "5" の間がこの例の唯一の例です。

上記のスワップの総数がいくつあるかを計算する必要があります。これは読者への演習として残しておきますが、ここで最後のヒントを 1 つ示します。リストの前半だけをループする必要があります。与えられた数に対するこれはまだですが、最終的には、リストの最初の半分の合計数に対して操作O(n^2)を行うだけでよく、それ以降の数は全体的にはるかに高速になります。O(n^2)

于 2012-07-10T21:22:23.147 に答える
0

分割統治を利用する

分割: シーケンス n のサイズをサイズ n/2 の 2 つのリストにする 征服: 再帰的に数える 2 つのリストを結合する: これはトリックの部分です (線形時間で行うため)

組み合わせて、マージとカウントを使用します。2 つのリストが A、B であるとします。これらは既にソートされています。A、B から出力リスト L を生成し、反転の数 (a,b) もカウントします。ここで、a は A にあり、b は B にあり、a > b です。

アイデアは、マージソートの「マージ」に似ています。2 つのソートされたリストを 1 つの出力リストにマージしますが、反転もカウントします。

a_i が出力に追加されるたびに、a_i はリスト B に残っているすべてのものよりも小さいため、新しい反転は発生しません。b_j が出力に追加された場合、それは A の残りのすべての項目よりも小さいため、a_i の数を増やします。 A に残っている要素の数による反転の数。

マージアンドカウント(A,B) ; A,B 2 つの入力リスト (ソート済み) ; C 出力リスト ; i,j 各リストへの現在のポインタ、先頭から開始; i, j が指す a_i, b_j 要素。反転のカウント数、初期値は 0

while A,B != empty 追加 min(a_i,b_j) if b_j < a_i count += A に残っている要素の数 j++ else i++ ; 現在、1 つのリストは空です リストの残りを C に追加します return count, C

マージ アンド カウントを使用すると、カウント反転アルゴリズムを次のように設計できます。

sort-and-count(L) L の要素が 1 つの場合は 0 を返す そうでない場合は、L を A、B に分割します (rA, A) = sort-and-count(A) (rB, B) = sort-and-count(B) (r, L) = merge-and-count(A,B) return r = rA+rB+r, L

T(n) = O(n lg n)

于 2015-11-25T23:52:06.113 に答える