ArrayList中恆時間和線性時間訪問

Question

我一直在學習Java SE 7的提示我看了一份聲明中關於ArrayList：

• 訪問在固定時間執行。
• 插入/缺失在線性時間執行。

我想知道什麼是不斷和線性時間訪問？

Answer 1

恆定時間意味着每個操作將花費多少時間來執行硬約束。

線性時間意味着ArrayList（包含的對象越多）所需的時間越長。連接是線性的，即time(op) <= CONST * #elements

在複雜的分析，我們稱它作爲big O notation和線性時間爲O(n)，提供固定時間爲O(1)

---

它的原因是：

• 訪問是普通的數組訪問，並且它在RAM機器中（例如，在PC機中）在不變的時間內完成。
• 插入/刪除 - 如果它不在最後一個元素中，需要移動所有下列元素:(插入請求向右移動，向左刪除） - 因此實際上需要線性數量的OP來執行插入/刪除（除非它是最後一個元素）

Answer 2

含義是：

• 恆定意味着時間總是相同的，它並不重要的列表的長度。

  [恆定時間也被稱爲O（1）在Big-O notation]

• 線性意味着越列表的增長，較長是時間，但以線性方式，所以例如，要在包含20個元素的列表上執行線性操作，則需要兩次包含10個元素的列表所需的時間。

  [線性時間也被稱爲爲O（n）在Big-O notation]

  甲precisation：比較算法時通常提供的最壞情況性能，所以這意味着所需的時間少或等於線性。

在你的情況列表的實現是基於陣列（這樣的名字的ArrayList）是這樣的：

的訪問時間是因爲當程序知道在哪裏不變列表的第一個元素是，每個單元格有多大，它可以使用簡單的數學運算式直接得到：

element_n_cell = element_1_cell + (cell_size * n) 

個

插入和刪除更多的時間，昂貴的原因有兩個：

1. 當您插入或在一個位置刪除元素，所有的以下內容需要轉移。

2. 數組不能改變大小，所以當你實例化一個新的ArrayList，Java將創建一個數組與預先定義的長度小號，只要它符合它會使用相同的陣列。當你添加（s + 1） -th元素時，程序需要創建一個更大的數組並複製新數組中的所有元素。