2

次のコードには、ユーザーが作成したスタック データ構造の 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];
    }
 }

私の本では、これら 2 つのコンストラクターの Big(O) はO(N)であると述べられていますが、インストラクターはO(1)であるべきだと教えようとしました。

O(1)ではなくO (N)である理由を誰かが説明してくれませんか?

4

3 に答える 3

1

より多くのメモリを割り当てる場合でも、メモリの割り当てにそれほど時間がかかることはありません。、などの間new Object[100];に検出できない違いがあります。これは、スタックを構築するために使用しているアルゴリズムがではなくであることを示します。new Object[1000];new Object[100000];O(1)O(N)

于 2013-10-26T16:04:36.690 に答える