complexity-theory - 运行时复杂度 : sorting 2d array where each row, 列和对角线是否排序？

Question

给定以下二维数组:

6   8   11  17
9   11  14  20
18  20  23  29
24  26  29  35

每一行和每一列都被排序，对角线也被排序(从左上到右下)。假设我们在数组中有 n² 个元素(在本例中为 n = 4)，使用需要 O(n² log(n²)) = O(n² log(n)) 的快速排序是微不足道的。对二维数组进行排序。我的问题是我们可以在 O(n²) 中对此进行排序吗？ ?

目标是使用给定的半排序二维数组并提出一个聪明的解决方案。

目标输出是:

6   8   9   11
11  14  17  18
20  20  23  24
26  29  29  35

Answer 1

是的，我们可以在 O(n^2) 时间内对其进行排序。

减少对一维数组进行排序

让我们首先证明这个对二维数组进行排序的新问题(使得每一行、每列和从左上到右下对角线都排序)可以简化为对 n^2 的一维数组进行排序的问题元素。

假设我们有一个由 n^2 个元素组成的已排序的一维数组。通过将前 n 个数字设置为第一行，然后将接下来的 n 个数字设置为第二行，我们可以轻松地将其重新排列为一个已排序的 n x n 数组，并重复直到我们用完数组。

因此，给定一个包含 n^2 个数字的二维数组，我们可以在 O(n^2) 时间内将其转换为一维数组，对该数组进行排序，然后在 O(n^2) 时间内将其转换回所需的二维数组.因此，如果我们能在 O(n^2) 中找到一个一维数组的排序算法，我们就可以在 O(n^2) 时间内等效地解决这个新问题。

在线性时间内对一维数组进行排序

鉴于此，我们只需要提供线性时间排序。即给定 n^2 个元素，在 O(n^2) 时间内对它们进行排序。方便的是，您可以使用多种算法来完成此操作，例如 counting sort或 radix sort ，尽管它们确实带有各种警告。然而，假设给定要排序的项目数量，数值范围是合理的，这些排序将在线性时间内运行。

因此，给定 nxn 数组中的 n^2 个元素，这个二维排序问题可以在 O(n^2) 时间内简化为一维排序问题，然后可以在 O(n^2) 中使用各种线性时间排序算法来解决时间。因此，总的来说，这个问题可以在 O(n^2) 时间内解决。

使用比较排序进行排序

继评论中的讨论之后，下一步是问:比较排序怎么样。比较排序是有益的，因为它可以让我们避免前面提到的计数和基数排序的警告。

然而，即使有这些附加信息，线性时间比较排序在实践中也是不太可能的，因为这需要我们在 O(1) 时间内计算每个数字的最终位置。我们知道使用比较排序是不可能的。

让我们考虑一个小例子:最初在第 1 行第 2 列的数字的最终排序位置应该是什么？我们知道它必须是第 2...n 列中的第一个数字。但是，我们不知道它相对于第 1 列中的数字(第 1 行第 1 列中的数字除外)属于何处。

通常，对于原始正方形中的任何数字，我们不确定其最终排序位置相对于其左下角的所有数字和右上角的数字。需要 O(log_2(n)) 次比较才能找到每个数字的相对位置，并且需要定位 O(n^2) 个数字。这种不确定性使我们无法在实践中实现线性时间排序。

但是我们拥有的额外信息应该能让我们实现一些加速。例如，我们可以调整 merge sort到这个问题。在标准的归并排序中，我们首先将原始数组分成两半并重复，直到我们得到保证排序的大小为 1 的数组，
然后我们反复合并这些子数组，直到我们有一个单一的数组。对于 n^2 个元素，我们必须创建一个具有 log_2(n^2) 层的二叉树，并且每一层都需要 O(n^2) 的时间来合并。

使用问题设置中的附加信息，我们不必拆分数组，直到它们的大小为 1。相反，我们可以从 n 个长度为 n 的排序数组开始，然后从那里开始合并。这将我们必须合并的层数减半，并为我们提供了 O(n^2 log_2(n)) 的最终运行时间。

结论

在实践中，这个额外的信息允许比较排序的一些加速，使我们能够实现 O(n^2 log_2(n)) 的运行时间。

但是为了实现在 O(n^2) 时间内运行的线性时间排序，我们必须依赖于诸如计数或基数排序之类的算法。