什么算法适合我，有问题

本文关键字：有问题 算法 什么 | 更新日期: 2023-09-27 18:33:29

我有一个矩阵[M x N]，在矩阵的每个单元格中，都有一个数组[N](从最大到最小排序(。

我必须编写一个函数，将这个Matrix重建为一个data-structure，从最小到最大排序？

具有最佳的内存和时间。

我的解决方案不是最佳的，而且成本非常高(内存和时间(。
Solution: 遍历矩阵并将每个数组拉到一个数组：O(N^2 - memory&time(之后对这个数组 O(N - 内存和时间(进行排序。

哪种算法最适合我？

什么算法适合我，有问题

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

我还没有计算过它的表现如何，但我认为它很好。附带说明一下，我认为您无法实现同时具有最佳内存和时间利用率的解决方案，您必须首先关注其中一个，然后使另一个尽可能好。

更新：您可以对此解决方案进行的一项改进是使用尾递归，重写它以使用尾递归应该不难。

您基本上是在尝试实现合并排序，但部分子案例已经排序。 如果你只是像合并排序那样递归合并列表对，并且假设你实际上的意思是列表的长度与矩阵端的长度大致相同，那么你的运行时间是 O(n^3 log(n^2(( 而不是你最初的建议是 O(n^3 log(n^3((， 或者它的速度提高了大约 33%(我在这里严重滥用了 bigO 表示法(。

你说的算法不可能有O(N^2)的时空复杂度。我在下面指定了我的分析：

算法 1 - 复杂度：O(M N^2log (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(MN^2 ×log MN(

改编自 n 路合并算法

  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}th array(， {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) 空间用于优先级队列。

相关文章：