java如何通过具体示例确定大O性能？

Question

我似乎一直在努力用代码中的以下方法确定Big O性能：isEmpty（）、peek（）、pop（）、push（）和size（）

我的ArrayStack程序中的所有这些方法的性能都是大O（1）。若然，原因为何？若否，原因为何

public class ArrayStack<E> implements Stack<E> {
   private E[] data;
   private int top = -1;
   private static final int DEFAULT_CAPACITY = 10;

   @SuppressWarnings("unchecked")
   public ArrayStack() {
      data = (E[]) new Object[DEFAULT_CAPACITY];
   }

   public E pop() {
      if (isEmpty()) {
         throw new EmptyStackException();
      }
      // allow garbage collection
      E save = data[top];
      data[top] = null;
      top--;
      return save;
   }

   public E peek() {
      if (isEmpty()) {
         throw new EmptyStackException();
      }
      return data[top];
   }

   public void push(E item) {
      if (data.length == size()) resize(2 * data.length);
      data[++top] = item;
   }

   public boolean isEmpty() {
      return top == -1;
   }

   public int size() {
      return top + 1;
   }

   @SuppressWarnings("unchecked")
   private void resize(int newCapacity) {
      E[] newdata = (E[]) new Object[newCapacity];
      for (int i = 0; i <= top; i++) {
         newdata[i] = data[i];
      }
      data = newdata;
   }

   public static void main(String[] args) {
      Stack<Integer> s = new ArrayStack<>();
      System.out.println("Size: " + s.size());
      for (int i = 0; i < 500; i++) {
         s.push(i*i);
      }
      System.out.println("Size: " + s.size());
      while (!s.isEmpty()) {
         System.out.print(s.pop() + " ");
      }
      System.out.println();
      System.out.println("Size: " + s.size());

      Stack<String> strings = new ArrayStack<>();
      String[] data = {"dog", "cat", "no", "geek", "computer"};
      for (String word: data) {
         strings.push(word);
      }
      while (!strings.isEmpty()) {
         System.out.print(strings.pop() + " ");
      }
      System.out.println();
   }

}

Answer 1

方法中完成的工作量不随堆栈中元素的数量而变化，也不随调用次数而变化

你可以看到这些方法所做的功是恒定的。这正是O（1）所代表的

另一方面，如果你考虑你的“Resiz（）”，当它达到一个特定的大小时，你正在复制已经存在的每个元素到一个新的位置。因此，所做的功与已经存在的元素数量成正比。如果有1000个元素存在，那么如果只有10个元素存在，将会有更多的工作。因此，该调用的运行时复杂性是O（N），其中N是堆栈中已经存在的元素数

但如果考虑调整后的摊销成本，则仍然是o（1），如 n-1 倍< n它在做恒定的工作。