algorithm - 分而治之算法对列表进行排序，其中每个元素距离其排序位置为 root(n)

Question

我被困在一个问题上，我只需要一个大致方向的提示/点(不要求答案)

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

几乎排序的意思是给定列表

x_1, x_2, .... x_n

如果排序后的列表用

表示

y_1, y_2, ... y_n

并且对于每个 i, j <= n 此属性都得到尊重:

x_i == y_j && |i-j| <= root(n)

我唯一想到的是在每个级别将列表划分为 root(n) 组(这将导致它们在第一次拆分时的最大长度为 root(n))，但我没有太确定从那里去哪里了，因为您必须在递归备份时一次加入 root(n) 个元素。

我还发现递归复杂度方程为:

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

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

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

编辑:所以据推测这是正确的答案。

Our algorithm is as follows: If n > 1, then we recursively sort each of the two (approximate) halves of the sequence; now all the elements are in the correct position, except possibly those within √n positions of the middle (do you see why this is true?); so we now do a merge of the elements in those positions. If we let T(n) be the time used to sort nelements, then for n > 1 we have

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(r*r) 时间内对 r 个项目的 r 个列表进行排序，只需连接列表(并在必要时修饰元素)。然而，众所周知，对于 n = r * r，你不能比 O(r*r*ln(r)) 或 O(n * ln(n)) 做得更好。

我猜要么是原始问题有点不同，要么是给你原始问题的人在计算复杂性时犯了一个错误。例如，假设当列表分为两半时，两部分仍然几乎已排序。 (有很多方法可以用这种方式拆分列表，比如每隔一个元素取一次，但并不是列表的每个分区都会有这个属性。)