什麼算法適合我，有問題？

我有一個矩陣[M×N]，在矩陣的每個單元格中，都有一個數組[N]（從最大到最小分類）。什麼算法適合我，有問題？

我必須寫下令從最小到最大的是重建這個Matrix一個data-structure功能，？

具有最佳內存和時間。

我的解決方案不是最優的，成本也非常高（內存&時間）。
Solution: 迭代矩陣和每個陣列拉至一個陣列：O（N^2 - 存儲器&時間）那種此數組ø後（N - 存儲器&時間）。

什麼算法最適合我？

來源

2013-10-02 IamStalker

當您合併已排序的列表時，類似[比賽排序]（https://en.wikipedia.org/wiki/Tournament_sort）可以提供幫助。 – SWeko

我不明白。既然你有'N^3'元素，並且需要對它們進行排序，那麼在內存和時間上都不會比'N^3'好。而你說你有'N^2'「非最佳」解決方案。 – Mikhail

您是否嘗試過一些合併技術？可能會逐一合併每個單元格，當所有行都完成後，您可以將行結果合併到一起。 –

這個答案可能有點偏離主題，因爲它使用f＃而不是c＃，但是該算法可以被重用，但我認爲用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]

我還沒有計算它如何執行，但我認爲這是一刀好。在旁註中，我認爲你不能實現既有最佳內存又有時間利用率的解決方案，你必須首先關注其中的一個，然後儘可能使其中一個最好。

UPDATE： 一個你可以做這個解決方案的改進是使用尾遞歸，它不應該是很難改寫它使用尾遞歸。

來源

2013-10-02 12:09:57

你可以把它翻譯成C＃嗎？ – IamStalker

@IamStalker也許以後，現在沒時間了。在c＃中執行它比f＃中的冗長得多。如果你提供你的起始數據結構，那麼編寫它就會少得多，所以請提供你的問題。 –

你基本上是試圖實現合併排序，但部分子案例已經排序。如果你只是按合併排序的方式遞歸地合併列表對，並且假設你實際上意味着列表的長度與矩陣的長度大致相同，那麼你的運行時間是O（n^3 log（ n^2））而不是你最初的建議是O（n^3 log（n^3）），或者它大約快33％（我在這裏嚴重地濫用了bigO符號）。

來源

2013-10-02 12:59:11 DanielV

這就是我提供的解決方案:)。 –

您談論的算法不可能具有O(N^2)的時間和空間複雜性。我指定我下面的分析：

算法1 - 複雜度：O（M N^2日誌（M N^2））

這是你所描述的算法。

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）

從Algorithm for n-way merge

適於通過每個陣列創建一個優先級隊列
迭代在MxN陣列中
1. enq ueue對（nextNumberIn（{I，J}個陣列），{I，J}）使用所述第一值作爲優先鍵
雖然隊列不爲空
1. 出隊頭（number，{I ，隊列j的}）
2. 輸出number
3. 如果{I，J}個陣列未被耗盡
  1. 排隊（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)來存儲新的數組。除此之外，算法＃1將需要大約O(log (M*N^2))額外的空間用於排序步驟，而算法＃2將需要用於優先級隊列的額外空間O(M*N)。

來源

2013-10-02 13:27:25 AbdullahC

什麼算法適合我，有問題？

回答

相關問題