什么算法适合我，有问题吗？

Question

我有一个矩阵M，在矩阵的每个单元格中，都有一个数组N。

我必须编写一个函数，将这个Matrix重构成一个data-structure，从min到max？

拥有最佳的记忆和时间。

我的解决方案不是最优的，而且成本极高(内存和时间)。

Solution:迭代矩阵并将每个数组拉到一个数组中: O(N^2 -内存和时间)，然后排序这个数组O(N -内存和时间)。

哪种算法最适合我？

Answer 1

这个答案可能有点离题，因为它使用的是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]

我还没有计算它的表现，但我认为它很好。顺便提一句，我不认为您能够实现一个同时具有最佳内存和时间利用率的解决方案，您必须先将其中一个集中在其中一个，然后尽可能地使另一个更好。

更新:可以对此解决方案进行的一个改进是使用尾递归，将其重写以使用尾递归应该不会那么困难。

Answer 2

您基本上是在尝试实现合并排序，但是已经对部分子案例进行了排序。如果您只是递归地合并列表对(合并排序的方式)，并且假设您实际上意味着列表的长度与矩阵侧的长度大致相同，那么您的运行时间是O(n^3 log(n^2))，而不是您最初的建议O(n^3 log(n^3 log(n^3)，或者它大约快33% (我在这里严重地误用了bigO符号)。

Answer 3

您所讨论的算法不可能具有O(N^2)的时间和空间复杂性。我详细说明了我的分析如下：

(MN^2))算法1-复杂度: O(MN^2 log )

这就是你描述的算法。

1)迭代矩阵并将每个数组拉到一个数组中:复制所有元素需要O(M*N^2)时间

2)在这类数组之后。最快的排序可能是O(M*N^2 log (M*N^2))。

因此，整个时间复杂度将是O(M*N^2 log (M*N^2))。

MN)算法2-复杂度: O(MN^2×log )

改编自https://stackoverflow.com/a/5055937/336656

1. 创建优先级队列
2. 在MxN数组中迭代每个数组
   1. 使用第一个值作为优先级键对对(nextNumberIn({i，j}数组)，{i，j})排队

​

1. 虽然队列不是空的
   1. 队列的去队列头(number，{i，j})
   2. 输出number
   3. 如果{i，j}数组没有耗尽
      1. nextNumberIn( {i，j}数组)，{i，j}

​

​

由于向优先级队列添加元素可以在对数时间内完成，所以第2项是O(M*N × log M*N)。由于时间循环的(几乎所有)迭代都添加了一个元素，所以整个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)空间。