arrays - 证明这样的算法不存在

Question

我正在努力为以下陈述寻找证明。证明没有基于比较的算法接收 n 大小的数组并发出相同元素的数组，其中索引中找到的所有元素除以 3 现在以线性时间在这些索引中以排序形式出现。

例如数组:8 6 1 3 0 9 4

执行算法后，数组将如下所示:3 6 1 4 0 9 8

最初元素 8、3、4 出现在数组中的索引是 3 的倍数，执行算法后它们仍然会出现在索引中是 3 的倍数，但这次它们将以排序后的形式出现在本例中为 3,4,8。

我需要证明这样的算法不存在。我试着假设那个陈述是正确的，这样在某些时候我会遇到矛盾，但它对我没有用。谢谢你的帮助。

Answer 1

有两个论据证明这种算法不存在。首先，正如评论中指出的那样，如果确实存在这样的算法，那么您可以执行以下操作:

1. 在 0 mod 3 个元素上运行算法
2. 在 1 mod 3 元素上运行算法
3. 在 2 mod 3 元素上运行算法
4. 合并三个列表以创建一个完全排序的数组。

前三个步骤中的每一个都将在 O(n/3) 时间内运行，最后一步将在 O(n) 时间内运行。那会给你一个 O(n) 比较排序算法。但比较排序被证明是 O(n log n)。

第二个参数是给定一个包含 n 项的数组，您希望在 O(n) 时间内对 n/3 项进行排序。如前所述，比较排序是 O(n log n)。所以排序 n/3 项目将是 O((n/3) * log(n/3))。因此，要在 O(n) 时间内对 n/3 项进行排序，log(n/3) 必须小于 3。8 的以 2 为底的对数等于 3。因此，如果 n > 24 ，然后对 n/3 项进行排序将需要超过 O(n) 次比较。