gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-02 01:35:05 24 4
gpt4 key购买 nike

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

 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)吗?

最佳答案

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

关于java - 通用堆栈构造函数的 Big-O,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19608704/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com