1

タイトルが示すように、サイズ n の k 個の並べ替えられた配列をマージする下限の証明は何ですか? 境界が O(kn*log[k]) であることはわかっていますが、これはどのように達成されたのでしょうか? 決定木を使用して p 要素の配列をソートすることと比較しようとしましたが、この証明を実装する方法がわかりません。

4

3 に答える 3

1

可能な実装。要素ごとに並べられたペアを格納するヒープ データ構造
を 作成しましょう。それで(element, arrayIndex)

  1. 対応する配列インデックスを持つ各配列の最初の要素をこのヒープに追加します。
  2. 各ステップで、ヒープから最上位 (最下位) のペアを削除し、結果pに追加して、インデックス付きの配列の次の要素を持つp.elementペアをヒープに挿入します (空でない場合)。(next, p.arrayIndex)p.arrayIndex

「次の」要素を追跡するkには、対応する配列の次の要素を指すインデックス/ポインター/イテレーターを含む配列が必要です。

kいつでもヒープ内には多くの要素しかないため、ヒープのinsert/remove操作はO(log(k))複雑になります。すべての要素は、ヒープから 1 回挿入および削除されます。要素数は ですn*k。全体的な複雑さはO(n*k*log(k)).

于 2017-10-10T13:25:10.827 に答える
1

これを証明するのは非常に簡単です。マージソートの方法で考えてみてください。

サイズK*Nの配列をマージソートするには、 O(KN*log(K*N))が必要です。

ただし、配列サイズがNの場合はソートされていることがわかっているため、サイズ1の葉に到達する必要はありません。簡単にするために、 Kは 2 の累乗であると仮定 します。サイズ N の葉に到達するには、2 で何回割る必要がありますか? K回！



視覚化 ここに画像の説明を入力


したがって、log(k)ステップがあり、各ステップをマージするにはK Nのコストがかかり、log(k)ステップがあります。したがって、時間計算量はO(NK (log(K))


証明:
下限ではなく、より良い結果が得られると仮定しましょう。次に、サイズN*Kの未知の配列について、サイズNのサブ配列に到達するまでそれを 2 つに分割し、サイズNの各配列をNlog(N)時間で、合計ですべての配列Kでマージソートします。 *N*log(N)時間。

サイズ N の K 個の配列を並べ替えた後、それらをサイズN*Kのより大きな配列にマージする必要があります。これは、下限ではないと仮定したため、 O(NK*(log(K))よりも少ない料金で済みます。

最後に、比較モデルでは不可能な N*K*log(N*K)未満の複雑さでサイズ N*K の未知の配列をソートしました。したがって、サイズ N の K 個の並べ替えられた配列をマージしながら、 O(NK*(log(K))
よりも優れた結果を達成することはできません。

于 2017-10-10T12:58:04.237 に答える