2

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

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

4

3 回答 3

3

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

于 2013-10-26T15:58:45.813 回答
2

当您询问大 O 表示法时，需要考虑两个问题：

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

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

对于您的两个构造函数，第一个分配 O(1) 内存，第二个分配 O(N) 内存，其中 N 是maxSize。

但是分配 O(N) 内存，或者需要 O(N) 比较，与花费 O(N) 时间完全不同——虽然这显然很重要，但这是一个更加模糊的概念，需要考虑整个系统（缓存效应，垃圾收集，CPU调度等），而不仅仅是算法。

一般来说，分配 N 字节的内存需要 O(N) 时间似乎是近似正确的，无论是对于具有显式释放的经典 C 风格内存分配还是对于 Java 风格的垃圾收集系统（在 Java 中分配内存非常便宜，但是您分配的所有内存都必须进行垃圾回收，并且您必须考虑其摊销成本）。这仍然是一个有趣的研究问题；内存分配的时间复杂度有一些很好的指示。（HT 给 Patrick Kostjens 的链接。）

我很高兴你正在考虑这个问题，而不是盲目地相信你的书或你的导师。

于 2013-10-26T20:12:07.957 回答
1

如果您分配更多内存，则分配内存不会花费更长的时间。new Object[100];,new Object[1000];等之间会有无法察觉的差异new Object[100000];。这表明您用于构造堆栈的算法是O(1), 不是O(N)。

于 2013-10-26T16:04:36.690 回答