我有一个程序,使用整数数组来作为整数堆栈的数据结构。但是,由于数组必须定义元素数量,当用户调用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) 运行时?