59

k-way マージは、それぞれがサイズ n の k 個の並べ替えられた配列を入力として受け取るアルゴリズムです。すべての要素の単一の並べ替えられた配列を出力します。

これは、マージソートアルゴリズムの中心となる「マージ」ルーチンを使用して、配列 1 を配列 2 にマージし、次に配列 3 をこのマージされた配列にマージするというように、すべての k 個の配列がマージされるまで続きます。

このアルゴリズムは O(kn) であると考えていました。これは、アルゴリズムが k 個の配列 (それぞれの長さ n) を 1 回トラバースするためです。なぜO(nk^2)なのですか？

4

9 に答える 9

67

k 個の配列のそれぞれを 1 回走査しないためです。最初の配列は k-1 回トラバースされ、最初は merge(array-1,array-2) として、2 番目は merge(merge(array-1, array-2), array-3) として ... など.

その結果、k-1 が平均サイズ n*(k+1)/2 でマージされ、O(n*(k^2-1)/2) の複雑さが O(nk^2) になります。

あなたが犯した間違いは、マージが並列ではなく逐次的に行われることを忘れていたため、配列のサイズがすべて n ではないことです。

于 2012-06-14T03:31:45.903 に答える
47

実際には、最悪のシナリオでは、最初の配列ではn回、2 番目の配列では2n回、3 番目の配列では3n回の比較が行われ、すぐに(k - 1)nになります。
だから今、複雑さは単純になります

n + 2n + 3n + 4n + ... + (k - 1)n
= n(1 + 2 + 3 + 4 + ... + (k - 1))
= n((k - 1)*k) / 2
= n(k^2 - k) / 2
= O(nk ^ 2)

:-)

于 2013-02-14T12:34:55.110 に答える
16

これはどう：

ステップ 1: 配列 (1 と 2)、配列 (3 と 4) などをマージします。(2n の k/2 配列マージ、合計作業 kn)。

ステップ 2: 配列 (1,2 と 3,4)、配列 (5,6 と 7,8) などをマージします (4n の k/4 マージ、合計作業 kn)。

ステップ 3: 繰り返します...

log(k) のような「ステップ」があり、それぞれ kn 個の作業があります。したがって、完了した作業の合計 = O(knlog(k))。

それ以外の場合でも、配列のすべての要素を並べ替えるだけであれば、O(knlog(kn)) 時間ですべてをマージできます。

于 2013-12-06T02:16:06.387 に答える
7

k-way マージは、それぞれがサイズ n の k 個の並べ替えられた配列を入力として受け取るアルゴリズムです。すべての要素の単一の並べ替えられた配列を出力します。

このアルゴリズムは O(kn) だと思っていました

矛盾によってそれを反証することができます。k=m および n=1 のアルゴリズムを使用する m 項目の並べ替えアルゴリズムを定義します。仮説によると、ソートアルゴリズムは O(m) 時間で成功します。矛盾、ソートアルゴリズムには少なくともO（m log m）の最悪のケースがあることが知られています。

于 2013-07-13T16:12:37.010 に答える
6

毎回アイテムを 1 つずつ比較する必要はありません。ソートされたセット内の最新の K 個のアイテムを単純に維持する必要があります。最小のものを削除し、次の要素で再配置します。これは n.log(k) である必要があります

関連記事。免責事項：私はそれを書くことに参加しました

于 2013-02-06T23:53:54.783 に答える
3

一般的な実装では、k 個の並べ替えられた配列 {i_1、i_2、i__k} のそれぞれのインデックスの配列を保持します。各反復で、アルゴリズムはすべての k 配列から最小の次の要素を見つけ、それを出力配列に格納します。kn 反復を実行し、反復ごとに k 配列をスキャンしているため、全体の複雑さは O(k^2 * n) です。

ここにいくつかの擬似コードがあります:

Input: A[j] j = 1..k : k sorted arrays each of length n
Output: B : Sorted array of length kn

// Initialize array of indexes
I[j] = 0 for j = 1..k

q = 0

while (q < kn):
    p = argmin({A[j][I[j]]}) j = 1..k           // Get the array for which the next unprocessed element is minimal (ignores arrays for which I[j] > n)
    B[q] = A[p][I[p]]
    I[p] = I[p] + 1
    q = q + 1
于 2012-06-14T04:14:50.210 に答える
0

詳細を知りたい、またはこれについて助けが必要な人のために、Recurseの回答とフォローアップコメントを拡張します

  • k-1最後の配列は何もマージされていないため、マージのみが必要です
  • 算術数列の項を合計する式は役に立ちます。Sn=n(a1 + an)2

k配列とn要素の最初の 4 つのマージをステップスルーする

+-------+-------------------+-------------+
| Merge | Size of new array |    Note     |
+-------+-------------------+-------------+
| 1     | n+n  = 2n         | first merge  |
| 2     | 2n+n = 3n         |             |
| 3     | 3n+n = 4n         |             |
| 4     | 4n+n = 5n         |             |
| k-1   | (k-1)n+n = kn     | last merge  |
+-------+-------------------+-------------+

平均サイズを見つけるには、すべてのサイズを合計し、マージ数で割る必要があります ( k-1)。n最初の項を合計する式 を使用するとSn=n(a1 + an)2、必要なのは最初と最後の項だけです。

  • a1 =2n(第 1 項)
  • an =kn(最終項)

すべての項をそのように合計したいn=k-1(項の数)。数値を差し込むと、すべての項の合計の式が得られます

Sn = ( (k-1)(2n+kn) )/2

ただし、平均サイズを見つけるには、用語の数 ( ) で割る必要がありk-1ます。これにより、分子の がキャンセルされk-1、平均サイズが残ります。

(2n + kn)/2

これで平均サイズがわかったので、これにマージ数を掛けることができk-1ます。乗算を簡単にするために、/2を無視して、分子を乗算するだけです。

  (k-1)(2n+kn)
= (k^2)n + kn - 2n

この時点で、 を再導入できますが/2、支配的な用語が(k^2)*n

于 2020-11-25T19:32:04.620 に答える