如何通過具體示例確定Big O性能？

-1

我似乎一直在努力確定大O的表演，在我的代碼，這些方法：）的isEmpty（），PEEK（），流行（），推（忽略調整，和大小（）如何通過具體示例確定Big O性能？

都會的我的ArrayStack程序中的這些方法具有Big 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(); 
    } 

}

來源

2016-10-06 Derrik Antrium

是的，他們都是O（1）。爲什麼？因爲O（1）描述了它們的漸近時間複雜度。 –

問問自己以下問題：*如果堆棧包含1,000,000,000個元素，操作會花費更長時間？*如果答案爲否，則性能爲_O（1）_。如果後備數組需要擴展，只有'push（）'可能需要更長的時間，但總的來說，它不會，完全像['ArrayList']（http://docs.oracle.com）的add（）'方法。 com/javase/8/docs/api/java/util/ArrayList.html），其中性能稱爲*攤銷常量時間*，並且仍然是_O（1）_。 – Andreas

@Andreas謝謝，這使得它更容易理解！ –

在方法中完成的工作量不會隨堆棧中元素的數量而改變，也不會隨着調用次數而改變。

您可以看到在方法中完成的工作是不變的。這正是O（1）所表示的內容。另一方面，如果考慮到'resize（）'，當它達到特定的大小時，就是將已經存在的每個元素複製到新的位置。所做的工作與已經存在的元素數量成正比。如果存在1000個元素，那麼將會有更多的工作，然後如果只有10個元素存在。因此，該調用的運行時複雜度爲O（N）其中N是堆棧中已存在的元素的數量。

但是，如果我們認爲調整大小的攤餘成本，它仍然是O（1）在N-1超時的ň它做持續的工作。

來源

2016-10-06 20:42:57

如何通過具體示例確定Big O性能？

回答

相關問題