java是泛型堆栈构造函数的BigO

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];
    }
 }

现在在我的书中，这两个构造器中的大（O）表示为O（N），但我们的讲师试图告诉我们它们应该是O（1）

谁能给我解释一下为什么它是O（N）而不是O（1）

Answer 1

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

Answer 2

如果分配的内存较多，则分配内存所需的时间不会明显延长。在new Object[100];、new Object[1000];、new Object[100000];等之间可能存在无法检测到的差异。这表明用于构造堆栈的算法是O(1)，而不是O(N)

Answer 3

当您询问大O符号时，有两个问题需要考虑：

1. 什么是N？（对于nxn矩阵，是n n，还是n**2？）

2. 你测量的成本是多少？N项的合并排序需要O（N logn）比较；但是，如果要对字符串进行排序，则每次比较的成本取决于字符串的长度

对于两个构造函数，第一个分配O（1）内存，第二个分配O（N）内存，其中N为maxSize

但是，分配O（N）内存，或者需要O（N）比较，与占用O（N）时间完全不同——这显然是一个更为复杂的概念，需要考虑整个系统（缓存效果、垃圾收集、CPU调度等），而不仅仅是算法

一般来说，分配N个字节的内存大约需要O（N）个时间，无论是对于带有显式free的经典C风格内存分配，还是对于Java风格的垃圾收集系统（在Java中分配内存非常便宜，但是您分配的所有内存都必须进行垃圾收集，并且您必须考虑摊销成本）。这仍然是一个有趣的研究问题Time complexity of memory allocation有一些很好的指针。（HT向Patrick Kostjens发送链接。）

我很高兴你想到了这一点，而不是盲目地相信你的书或你的导师