1

私はマトリックス[M x N]を持っています。マトリックスの各セルには、配列[N]があります(最大から最小にソートされています)。

これをmin から max の順に再構築する関数をMatrix1に書く必要がありますか?data-structure

最適なメモリと時間で。

私のソリューションは最適ではなく、コストが非常に高くなります（メモリと時間）。
Solution: 行列を反復処理し、各配列を 1 つの配列にプルします: O(N^2 - メモリ & 時間) その後、この配列 O(N - メモリ & 時間) を並べ替えます。

自分に最適なアルゴリズムは?

4

3 に答える 3

1

この回答は、C# ではなく f# を使用しているため、少しトピックから外れている可能性がありますが、アルゴリズムは再利用できますが、f# で記述した方が速いと思いました。これは、質問へのコメントで説明されているように、すべての結果をマージするサンプル ソリューションです。

let rec orderedMerge xs ys =
    match xs,ys with
    | [],l | l,[] -> l
    | x::xs', y::ys' ->
        if x < y then x :: (orderedMerge xs' ys)
        else y :: (orderedMerge xs ys')

let rec orderNestedMerge xxs =
    match xxs with
    | x::[] -> x
    | x::y::[] -> orderedMerge x y
    | x::y::xxs' -> orderedMerge (orderedMerge x y) (orderNestedMerge xxs')

let rec orderNested2Merge xxxs = 
    match xxxs with
    | x::[] -> orderNestedMerge x
    | x::y::[] -> orderedMerge (orderNestedMerge x) (orderNestedMerge y)
    | x::y::xxxs' -> orderedMerge (orderedMerge (orderNestedMerge x) (orderNestedMerge y)) (orderNested2Merge xxxs')

let l1 = [1;5;6;10]
let l2 = [2;3;9;11]
let l3 = [3;4;5;8]
let l4 = [2;8;9;12]
let m1 = [l1;l2]
let m2 = [[l1;l2];[l3;l4]]
let r1 = orderedMerge l1 l2
let r2 = orderNestedMerge m1
let r3 = orderNested2Merge m2

結果：

val m1 : int list list = [[1; 5; 6; 10]; [2; 3; 9; 11]]
val m2 : int list list list = [[[1; 5; 6; 10]; [2; 3; 9; 11]]; [[3; 4; 5; 8]; [2; 8; 9; 12]]]
val r1 : int list = [1; 2; 3; 5; 6; 9; 10; 11]
val r2 : int list = [1; 2; 3; 5; 6; 9; 10; 11]
val r3 : int list = [1; 2; 2; 3; 3; 4; 5; 5; 6; 8; 8; 9; 9; 10; 11; 12]

私はそれがどのように機能するかを計算していませんが、かなりうまくいっていると思います. 余談ですが、最適なメモリと時間の使用率の両方を備えたソリューションを実装できるとは思いません。最初にそのうちの1つに焦点を合わせてから、もう1つを可能な限り改善する必要があります。

更新: このソリューションにできる改善の 1 つは、末尾再帰を使用することです。末尾再帰を使用するように書き直すことはそれほど難しくありません。

于 2013-10-02T12:09:57.983 に答える
0

基本的にマージソートを実装しようとしていますが、サブケースの一部はすでにソートされています。マージソートの方法でリストのペアを再帰的にマージするだけで、リストの長さが行列の辺の長さとほぼ同じ長さであると実際に意味していると仮定すると、実行時間は O(n^3 log( n^2)) O(n^3 log(n^3)) である元の提案よりも、または約 33% 高速です (ここで bigO 表記をひどく誤用しています)。

于 2013-10-02T12:59:11.207 に答える
0

あなたが話しているアルゴリズムは、おそらく時間と空間の複雑さを持つことはできませんO(N^2)。以下に私の分析を指定しました。

アルゴリズム 1 - 複雑度: O(M N^2 log (M N^2))

これはあなたが説明したアルゴリズムです。

1) マトリックスを反復処理し、各配列を 1 つの配列にプルします。O(M*N^2)すべての要素をコピーするには時間がかかります。

2) その後、この配列をソートします。ソートできる最も速いのは ですO(M*N^2 log (M*N^2))。

したがって、全体の時間計算量は になりますO(M*N^2 log (M*N^2))。

アルゴリズム 2 - 複雑度: O(M N^2 × log M N)

n-way マージのアルゴリズムから適応

  1. プライオリティ キューを作成する
  2. MxN 配列の各配列を反復処理します
    1. 最初の値を優先キーとして使用して、ペア (nextNumberIn({i,j}th array), {i,j}) をキューに入れます
  3. キューが空でない間
    1. numberキューの先頭 ( , {i,j}) をデキューする
    2. 出力number
    3. {i,j} 番目の配列が枯渇していない場合
      1. enqueue (nextNumberIn({i,j}番目の配列), {i,j})

プライオリティ キューへの要素の追加は対数時間で実行できるため、項目 2 はO(M*N × log M*N)です。while ループの (ほぼすべての) 反復で要素が追加されるため、while ループ全体は になりますO(M*N^2 × log M*N)。ここで、M*N^2 は並べ替える要素の総数です。

ステップ 3 の複雑さが支配的であるため、全体的な時間の複雑さは になりますO(M*N^2 × log M*N)。

スペースの複雑さ

上記の両方のアルゴリズムで、スペースの複雑さはO(M*N^2)、新しい配列を格納するために最小になります。それに加えて、アルゴリズム #1O(log (M*N^2))では並べ替えステップに約追加のスペースが必要ですが、アルゴリズム #2O(M*N)ではプライオリティ キュー用に追加のスペースが必要です。

于 2013-10-02T13:27:25.440 に答える