對Java的ArrayList

時間複雜度爲ArrayList數組或Java中的一個列表？獲取操作的時間複雜度是多少，是O(n)還是O(1)？對Java的ArrayList

2010-02-02 Hidayat

Java中的ArrayList是List，它由array支持。

的get(index)方法是恆定時間，O(1)，操作。

代碼直出Java庫ArrayList.get(index)的：

public E get(int index) { 
    RangeCheck(index); 
    return (E) elementData[index]; 
}

基本上，它只是返回一個值直出背襯陣列。（RangeCheck(index)）也是恆定的時間）

2010-02-02 08:10:42 jjnguy

這是恆定的時間，因爲array [n] ----意味着系統將只進行數學計算= offsetvalue +（變量的大小）* n 。所以這整個計算將在處理器中發生，而不會一次又一次地訪問內存位置。這就是爲什麼它是O（1） – 2013-06-09 14:37:38

它的實現是一個數組做和get操作是O（1）。

的javadoc說：

大小，的isEmpty，獲取，設置迭代器和操作的ListIterator中恆時間運行。添加操作運行在分期常量時間，即，添加N元素需要O（n）的時間。所有其他操作以線性時間（粗略地說）運行。與LinkedList實現的相比，常數因子較低。

2010-02-02 08:09:11 tangens

要迂腐，它是一個由數組支持的List。是的，get()的時間複雜度是O（1）。

2010-02-02 08:10:31

大家都已經指出的那樣，讀操作是不變的時間 - O（1），但寫操作必須支持數組中運行的空間，重新分配的潛力，副本 - 從而在O（n）的時間運行，因爲醫生說：

大小，的isEmpty，獲取，設置迭代器，的ListIterator和操作在固定時間運行。 添加操作以攤銷後的恆定時間運行，即添加n個元素需要O（n）時間。 所有其它操作的運行線性時間（粗略地說）。對於LinkedList 實施，與相比，的常數係數較低。

在實踐中，一些添加後，一切都是O（1），因爲每次容量耗盡時，支持數組都會加倍。所以如果數組從16開始，就會變滿，它會重新分配到32，然後是64,128等等，所以它可以擴展，但是GC可以在一個大的重新分配期間觸發。

2010-02-02 08:18:53

這有點偏離主題，但我會討厭某個人感到困惑，並沒有真正注意到重點**獲取**操作。 – 2010-02-02 08:19:56

在我看到的JDK代碼（1.6.0_17）中，新容量實際上按（oldCapacity * 3）/ 2 + 1計算。 – Adamski 2010-02-02 09:01:15

對第一句語句進行梳理，這似乎暗示寫操作在O n）時間。這不是文檔所說的，它說*添加n個元素需要O（n）*。對於單個元素，插入時間仍然是O（1）。重新分配，複製等只是使它有點「更大」O（1）。 – 2010-02-02 10:28:08

剛一說明。

的get(index)方法是一個常數時間，O(1)

但那樣的話，如果我們知道指數。如果我們嘗試使用indexOf(something)獲得索引，那麼這將花費O(n)

2018-02-02 09:23:35 prime

回答