3

行がソートされている nxm 行列があり、行列の数値を昇順に出力する必要があります。列は必ずしもソートされているわけではありません。私の頭に浮かんだ解決策は、マトリックス内の行を別々のリスト（基本的にはマージソートのマージステップ）と見なして単純にマージすることでした。マージソートではO（n）を取ります。この場合のように、n個の個別の配列をマージすることの複雑さを知りたかったのです。O(nxm) だと思ったのですが、よくわかりません。

また、数字を昇順で印刷するより良い方法は何でしょうか? 一度に n 個のリストをマージするか、すべての行を考慮するまで一度に 2 つのリストをマージしますか?

ありがとう！

4

1 に答える 1

1

What would be complexity? Its all depends how do you merge N arrays of M size!

マージの複雑さ：

  • 2つのソートされたサイズの配列のマージMは順番に行われます。したがって、このステップの複雑さはO（2M）です。

ここN rowsでeach row is sorted、要素が含まれていMます。

（線形にマージする）のように行う場合：

  • 最初に2つの行をマージします-中間になります2M size sorted array。
  • 2M array別のmatixとマージしrow of N sizeます-あなたは得るでしょう3M size sorted array。

takes N stepsこの方法でマージしcomplexity would be O(N*M)ます。

より良い方法（分割統治法）：

  • 最初に2つの連続する行のすべてのペアをマージします（1,2）、（3,4）これにより、2MサイズのN/2ペアが得られます。次のステップでペアワイズでマージします。以下に説明するように。

  • 最初に2行とのペアを作成しmerge all N/2 pairs first and merge themます。
    例：ペアrow（1,2）; 行（3,4）; row（5,6）......取得し= N/2 pairs each of 2M sizeます。

  • 次のステップで、make pair of two merged arrays each of size 2M from previous stepそれらをマージします- get N/4 sorted array of 4M size（（2Mと他の2Mアレイのマージ-> 4Mで、複雑さはO（2M + 2M）= O（4M））

このすべての中間体を段階的にマージしますsorted arrays util you gets a single sorted array of size N*M。そして今回の複雑さは合計としてM*N * log（N）steps required is log(N)になります。

マージソートとその複雑さを学ぶことをお勧めします。

于 2012-11-16T06:25:20.710 に答える