java - 通用堆栈构造函数的 Big-O

Question

以下代码包含用户创建的堆栈数据结构的两个构造函数。

 public class ArrayStack<T> implements BoundedStackInterface<T> {
    protected T[] stack;
    public final int defCap = 100;
    public ArrayStack() {
       stack = (T[]) new Object[defCap];
    }
 }

 public class ArrayStack<T> implements BoundedStackInterface<T> {
    protected T[] stack;
    public ArrayStack(int maxSize) {
       stack = (T[]) new Object[maxSize];
    }
 }

现在，在我的书中，这两个构造函数的 Big(O) 被描述为 O(N)，但我们的讲师试图告诉我们它们应该是 O(1)强>.

有人介意向我解释一下为什么它是O(N)而不是O(1)吗？

Answer 1

构造函数根据数组的长度分配内存量，数组被定义为构造函数的参数。分配此内存所需的时间与所分配的数组大小(以及内存量)成线性关系，因此 O(n)。 O(1) 意味着可以在恒定的时间内分配内存，而与数组的大小无关，这是不可能的。