如何反转一个非常大的数组？

Question

好的，我知道通过交换数组项直到达到中间来反转一个数组非常容易。像这样：

int array[SIZE];
int temp;

for (int i = 0; i < SIZE/2; i++)
  {
     temp = array[i];
     array[i] = array[SIZE-1 - i];
     array[SIZE-1 - i] = temp;
  }

但是如果数组的大小非常大，比如10000，是否有可能以O(N)的时间复杂度进行操作？

- Ege Kuzubasioglu

---

你现在正在进行O(N)操作。O()的整个意义在于N是未指定的。 - Jonathon Reinhart

你编写的代码已经是O(n)了。更准确地说，它运行了n/2次迭代。 - Shubham Chaurasia

好的，我明白了，但如果大小等于1000000，这个方法不会太慢吗？ - Ege Kuzubasioglu

如何在Java中编写正确的微基准测试？ - sp00m

如果您使用列表而不是数组，您可以编写一个在O(1)中查看列表的视图的程序。com.google.common.collect.Lists.reverse已经实现了这一点。 - cpp beginner

谢谢，我听说过Commons.Lang库ArrayUtils.reverse(int[]array)，它能用于字符串数组吗？ - Ege Kuzubasioglu

Answer 1

您无法比当前运行时间为O(n)的算法更快地完成它。可能感兴趣的是将数组包装在一个提供O(1)反转的类中：

一个简单的版本可以看起来像这样：

public class ReversableArray {
  private boolean reverse = false;
  private final int[] array;
  public ReversableArray(int[] array) { this.array = array; }

  public int get(int index) {
    return reverse ? array[array.length - index - 1] : array[index];
  }
  public void reverse() { reverse = !reverse; }
}

- assylias

Answer 2

反转一个数组的时间复杂度不能比O(n)更快。然而，你的代码的时间复杂度也是O(n)。

大O符号的定义：

大O符号的定义

不是无限大

或者我们可以说：

大O符号的另一种定义

存在一个常数c，使得c.f(x)大于g(x)对于所有x的值。

在这里，我们考虑n是我们数组的大小，函数T(n)是我们程序的步骤。

交换两个整数的成本是恒定的时间。进行n/2次交换将导致O(n)。

很抱歉没有在答案中包含图像。

- Sajad Banooie