1

1 行に 1 単語の単語を含むファイルを考えてみましょうN。ファイルが大きすぎるため、ファイル全体を一度にメモリに読み込むことができません。 私の答え：ファイルを.So
に分割します各チャンクのサイズ一度に 1つのチャンクをメモリに読み込み、ソートしてファイルに書き戻します.すべてのkチャンクをソートします. を実行します。 合計時間の複雑さを分析します。どうすればできますか？ 各チャンクのソートにかかる時間 = (クイックソートを使用すると仮定) k 個のチャンクをマージする時間 = (それは??) したがって、総時間の複雑さ = 時間の複雑さを分析する週k chunksx = N/k

k way merge

xlogx
klogk
??

4

1 に答える 1

1

各チャンクのサイズは N/k で、チャンクの数は k です。

したがって、合計時間の複雑さは

N/k チャンクの読み取り + これらのチャンクのそれぞれのソート、つまり O( N/k klogk) + それらの k チャンクの各 [部分] のマージ O( Nk ) + ファイルの書き込み。

したがって、IO 時間 + O(Nlogk) になります。

私もこれらのことを学んでいます...ここで間違っている場合は、誰かが私を分析して修正できれば素晴らしいと思います..

-パヴァン。

于 2012-06-21T18:01:03.303 に答える