在不到 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.