關於Big（O）性能的問題

所以我的數據結構類覆蓋了時間複雜度，我只是對arraylist和treemap的性能提出了一個簡短的問題。關於Big（O）性能的問題

爲ArrayList的get方法是O（1）和用於TreeMap的GET方法是O（log n）的現在

，如果我提出一個循環，通過整個列表或樹如

迭代

for (int i = 0; i < blahblah.size(); i++) 
{ 

blah blah 

}

對於數組列表，這個循環的性能是o（1）還是o（n）？我意識到，當你檢索1個項目時，性能是O（1），但是這個循環遍歷整個列表，所以它不會是1 * n個項目，這將使它成爲n？

與樹形圖相同的東西，它會是o（log n）或n log n，因爲你要經歷整個樹。

2011-03-05 jtn

1）它是大O不大哦，2）你應該用「算法」，「複雜性」而不是「java」來標記這樣的問題，因爲這不是語言特定的 – quasiverse 2011-03-05 03:15:00

@quasi固定''' – Earlz 2011-03-05 03:15:24

你的循環將會是O（n），因爲它會隨着元素的數量線性縮放。 n的倍數，你將有兩倍的迭代次數。 – seand 2011-03-05 03:27:37

是的，那就是O（n）。 O值幾乎總是最壞的情況。

2011-03-05 03:14:50 thomasfedb

不，他們並不總是最壞的情況。例如：在最差和最好的情況下，快速排序都是O（2^N）。 – 2011-03-05 03:30:51

我接受你的觀點，但你永遠不會說「這是O（1）因爲n可能是1」= P – thomasfedb 2011-03-05 04:12:11

Martinho是對的，你可以在大O符號中指定平均和最好的情況。） Nitpicking：quicksort的最好情況顯然是O（n log n）（我們得到一個log n級的調用樹，每個級別最多n個調用） – Voo 2011-03-05 04:13:32

-1

查看所有元素將是O(n)，因爲您必須至少訪問一次。

樹圖應該是O(n)以及出於同樣的原因考慮你是否以後序，順序或前序順序訪問節點。

2011-03-05 03:15:20 Argote

他說他想遍歷整個樹。在O（log n）時間顯然沒有辦法訪問n個元素。 – 2011-03-05 03:17:11

我誤解了這個問題，我認爲它與迭代的東西是分開的。 – Argote 2011-03-05 03:17:53

由於您需要數據結構的所有n個元素，因此結果不僅取決於給定的數據結構，還取決於您想要檢索的元素數量。

所以是的結果將是O（n）或O（n日誌n），但取決於數據結構，你可以做得更好。考慮一個鏈表 - 而不是得到O（n * n），你可以用O（n）完成。

但是，除了大O之外，還有更多的表現 - 常量在現實中很重要。一個例子是基數類型的32位數字。用於排序的O（n）聽起來不錯，但對於大多數合理的輸入大小，快速排序仍然會更快。

2011-03-05 03:18:15 Voo

好的，謝謝你們的快速回復。 :) – jtn 2011-03-05 03:27:08

「爲ArrayList的get方法是O（1）和樹形圖中get方法是O（log n）的」

原因ArrayList.get（）是O（1）是因爲索引裏只是從原點的偏移。如果數組有5或5M個元素，它的工作量是相同的，這並不重要。

TreeMap.get（）是O（log n），因爲它可能必須在二叉樹下向下遍歷多個元素。

2011-03-05 03:32:04 seand

回答