Array.copyOf() 的时间复杂度

Question

我有一个程序，使用整数数组来作为整数堆栈的数据结构。但是，由于数组必须定义元素数量，当用户调用push()方法时，如果超出数组初始大小，我必须重新分配原始数组到新的更大的数组，并调整大小。

例如：

    int[] data = new int[100];

当用户调用push()方法时，它会在必要时进行调整大小。

    public int push(int item) {
        if (size + 1 > data.length) { // O(n) solution
            data = Arrays.copyOf(data, data.length * 2 + 1); // double array size
        }
        data[size] = item; // size is elements from 0 to size that matter(as a stack)
        size++;
        return item;
    }

然而，我想知道：Arrays.copyOf() 的运行时复杂度是多少？我的测试似乎表明它在 O(n) 和 O(constant) 之间，但我仍不确定。如果它不是 O(constant)，是否有一种新的方法可以调整数组大小并保持此方法的 O(constant) 运行时？

- Jack L.

---

请查看 System.arrayCopy，它会更快。 - J.Miller

你可能需要考虑的一件事是，尽管复制有时会发生，但它作为一个罕见事件与实际时间复杂度的摊销运行时间不同。 - J.Miller

Answer 1

Array.copyOf的复杂度为O(n)。它内部使用System.arraycopy，其复杂度也是O(n)。

- Pankaj Sharma

---

O(n)和O(length)不是基本上一样的吗？因为n是数组中元素的数量。 - Jack L.

如果是这种情况，那么基本上没有办法在保持O（常数）运行时增加数组大小。我想我必须抛出IllegalStateException（“超过列表容量”），然后为该类拥有一个单独的构造函数，让用户从一开始就定义数组的大小。 - Jack L.

如果您只需要堆栈的推入/弹出操作，可以使用链表来避免大小扩展的成本。 - Pyranja