java - 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(常数) 之间，但我仍然不确定。如果它不是 O(constant)，是否有一种新方法可以调整数组大小，同时为该方法保持 O(constant) 运行时间？

Answer 1

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