10

nが常にmより大きい場合、サイズnとmの2つのソートされた配列をマージする時間の複雑さは何であるか疑問に思っていました。

私はマージソートを使用することを考えていました。この場合、O（log n + m）を消費すると思います。

私はビッグオーなどがあまり得意ではありません。この問題の時間計算量を提案し、問題を解決するためのさらに最適化された方法があるかどうかを知らせてください。

4

3 に答える 3

35

2つの並べ替えられたリストをマージする時間は、間違いなくO（m log n）ではありません。O（n + m）です。

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

allocate c with length n+m
i = 1
j = 1
while i < n or j < m
  if i = n
    copy rest of b into c 
    break    
  if j = m
    copy rest of a into c
    break
  if a[i] < b[j]
    copy a[i] into c
    i=i+1
    continue
  if b[j] < a[i]
    copy b[j] into c
    j=j+1
    continue

これで、cを割り当てるのに十分なメモリがない場合でも、ほとんどのハードウェア（RAMとハードディスクの両方）でブロック操作が可能になるため、これをO（n + m）時間になるように変更できます。配列の中央に単一のアイテムを挿入する必要がある場合、スペースを空けるためにブロックの最後尾を1つ上に移動するのは1回の操作です。これを許可しないハードウェアを使用している場合は、挿入ごとにO（n）が必要になる可能性があります。これは、O（n + mn）の複雑さです。小さい配列の要素を大きい配列に挿入するだけでよいので、大きい配列の要素がすでに正しい場所にある場合は、大きい配列の断片をシフトする必要はありません。したがって、nは同じままで、mビットの複雑さが増します。これは、長さmの配列bがすべて長さnの配列aの前に適切に配置されている場合に示される最悪のケースです。

于 2012-10-08T14:41:45.613 に答える
3

この問題を自分で経験するだけで、Big OはそうではなくO(m+n)、実際にはただのことO(n)です。

擬似コードの理由は次のとおりです:(注：このコードは、m>nまたはm== nの場合を処理するために作成しました）

Merging sorted arrays A and B into C.
let ints 'i' and 'j' and 'k' = 0

while(i < A.length && j < B.length){
    if(A[i] < B[j]){
        C[k] = A[i]
        i++
    } else {
        C[k] = B[j]
        j++
    }
    k++
}

// Copies rest of A into C if A.len > B.len
while(i < A.length){ 
    C[k] = A[i]
    k++
    i++
}

// Copies rest of B into C if A.len < B.len
while(j < B.length){ 
    C[k] = B[j]
    k++
    j++
}
return C

これで、長さnの配列が長さmの配列よりも大きいことがわかります。これは、長さmの配列内のすべての要素が長さnの配列内のすべての要素よりも大きくなる可能性があることを意味します。ただし、n> m（A[2,3,4,5,6]andなどB[7,8,9]）であっても、問題ではありません。最初のループは、それぞれの配列の長さiまたは同じ長さになるまで繰り返され、その後、残りのAまたはBがCに追加されるまで、次の2つのwhileループの1つだけが実行されます。j

したがって、最終的にどのようになるかがわかりますO(m+n)が、Big Oは通常、最悪の場合の実行時間を処理します。したがって、配列内の要素の構成に関係なく、長さnの配列をmよりも多く繰り返すことがわかります。、したがって、mは常にn未満になります。したがって、mをドロップして取得しますO(n)。

これは、nが無限大に等しくなる可能性があるためです。したがって、それが可能であるため、mが無限大になることはなく、定義上、無限大未満でなければならないという事実がわかります。したがって、さらに定義すると、n（nだけが無限大になる可能性があるため、ある時点で無限大に成長しなくなるためです）。また、Big Oランタイムを決定するときに定数を削除するため、を取得しO(n)ます。

明らかに私はパーティーに数年遅れています、笑、しかし私はそれが将来これに出くわすかもしれない他の誰かのために空気をきれいにすることを願っています:)

于 2020-08-31T00:08:56.577 に答える
-13

注意！この回答にはエラーが含まれています

より効率的なアルゴリズムが存在し、それは別の回答で提示されます。

複雑さはO（m log n）です。

長い配列を呼び出しa、短い配列を呼び出すと、b説明したアルゴリズムは次のように記述できます。

  for each x in b
      insert x into a

ループはm回繰り返されます。ソートされた配列への各挿入は、O（log n）操作です。したがって、全体的な複雑さはO（m log n）です。

ソートされているためb、上記のアルゴリズムをより効率的にすることができます

  for q from 1 to m
      if q == 1 then insert b[q] into a
      else 
         insert b[q] into a starting from the position of b[q-1]

これにより、漸近的な複雑さが増す可能性がありますか？あまり。

bからの要素がに沿って均等に広がっていると仮定しますa。次に、各挿入が必要にO(log (n/m))なり、全体的な複雑さはになりますO(m log(n/m) )。k>1に依存しない定数が存在する場合、nまたはmそのようなものが存在するn > k * m場合O(log(n/m)) = O(log(n))、上記と同じ漸近的な複雑さが得られます。

于 2012-06-14T18:48:14.147 に答える