algorithm - 分治算法对列表进行排序，其中每个元素距其排序位置的根（n）

Question

我被一个问题困住了，我只需要一个大方向的提示/点（不要求答案）

该问题询问分治算法的详细信息，该算法给定几乎已排序的序列，在时间 O(n) 内产生正确的顺序。

他们所说的几乎排序的意思是给定列表

x_1, x_2, .... x_n

如果排序列表由

y_1, y_2, ... y_n

并且对于每一个 i, j <= n 这个属性都受到尊重：

x_i == y_j && |ij| <= 根（n）

我想到的唯一一件事是将列表划分为每个级别的 root(n) 组（这将导致它们在第一次拆分时最多为 root(n)），但我不太确定在哪里从那里开始，因为您必须在递归备份时一次加入 root(n) 元素。

我还发现递归复杂度方程是：

T(n) = root(n) * T(n/root(n)) + d * root(n)

可以master's theorem证明是 O(n) 时间。

所以看起来我在拆分方面走在正确的轨道上，我只是不确定是否应该以特殊方式拆分或比较某种方式或什么。

编辑：所以据说这是正确的答案。

我们的算法如下：如果 n > 1，那么我们递归地对序列的两个（近似）半部分中的每一个进行排序；现在所有元素都在正确的位置，除了中间的√n个位置（你明白为什么这是真的吗？）；所以我们现在对这些位置的元素进行合并。如果我们让 T(n) 是用于对 n 个元素进行排序的时间，那么对于 n > 1，我们有

T(n)≤2T(⌈n=2⌉) +c * √n

由于 √(n) = n ^.5和 .5 < 1 = log ₂ 2，分治循环的主定理告诉我们 T(n)∈O(n)。

我不确定我是否同意，因为对两半进行排序的时间是 O( ⁿ ⁄ ₂ * log( ⁿ ⁄ ₂ ))，结果是 O(n*logn)，最终合并是 O(√ n * √n) 这是 O(n) 给我们总共 O(n*logn + n) -> O(n*logn)

Answer 1

我认为基于比较的排序不可能在O(n).

考虑一个简化的问题，将排序后的数组分成√n个桶，每个桶内的元素被打乱。满足每个元素距离其最终点不超过 √n 个位置的条件。

要解决此问题，您必须对每个存储桶进行排序。使用任何O(n*logn)排序，你都会有 √n * (√n*log√n)。这是 (1/2)*n*logn，仍然是O(n*logn).

由于这个简化的问题只能在 中解决，因此我得出结论，使用基于比较的排序O(n*logn)不可能解决原始问题。O(n)

例如，如果您知道所有元素都是某个范围内的整数，那么您将不再局限于基于比较的排序，并且可以O(n)使用非基于比较的排序（例如鸽子排序）来解决问题。

Answer 2

这种算法可用于在 O(r*r) 时间内对 r 个项目的 r 个列表进行排序，只需将列表连接起来（并在必要时装饰元素）。但是，众所周知，对于 n = r * r，您不能做得比 O(r*r*ln(r)) 或 O(n * ln(n)) 更好。

我想要么是原始问题有点不同，要么是向您提供原始问题的人在计算复杂性时犯了错误。例如，假设当列表分成两半时，两部分仍然几乎是 sorted。（有很多方法可以以这种方式拆分列表，例如获取每个第二个元素，但并非列表的每个分区都具有此属性。）

Answer 3

第一条线索：T(n) = root(n) * T(n/root(n)) + d * root(n) 不正确。因为它是一个递归函数，所以它不适用于 T(root(n))。