arrays - 在不到 O(n) 的时间内反转数组的子数组

Question

我们如何在不到 O(n) 的时间内反转数组(或任何其他数据结构，如链表(非双重))的子数组(比如从第 i 个索引到第 j 个索引) ？ O(n) 时间消耗是微不足道的。(我想在数组上多次进行这种反转，比如从头开始并反转 n 次(每次，前进一个索引然后再次反转)，所以应该有一种方法，它的摊销分析会给我们带来少于 O(n) 的时间消耗，知道吗？
提前致谢:)

Answer 1

我认为您想用错误的方法解决这个问题。我猜你想从整体上改进算法，而不是 O(n) 逆向的东西。因为那是不可能的。如果您必须考虑 n 个元素中的每一个，那么您的复杂度总是 O(n)。

正如我所说，您可以做的是改进 O(n^2) 算法。您可以在 O(n) 中解决该问题:假设我们有这个列表:

a b c d e

然后您使用您的算法修改此列表:

e d c b a
e a b c d

等等..最后你有这个:

e a d b c

如果你有两个指针来自数组的两端并且在指针之间交替(递增/递减/获取值)，你可以获得这个列表。整个过程的复杂度为 O(n)。

这个算法更详细的解释:

使用前面的列表，我们希望元素按以下顺序排列:

a b c d e
2 4 5 3 1

所以你创建了两个指针。一个指向列表的开头，另一个指向列表的结尾:

a b c d e
^       ^
p1      p2

然后算法的工作原理如下:

1. Take the value of p2
2. Take the value of p1
3. Move the pointer p2 one index back
4. Move the pointer p1 one index further
5. If they point to the same location, take the value of p1 and stop.
   or if p1 has passed p2 then stop.
   or else go to 1.