在ArrayList的開頭添加一個元素的時間複雜度是多少？

說我有具有n個元素的ArrayList的本陣，和我在開始添加元素：在ArrayList的開頭添加一個元素的時間複雜度是多少？

myArrayList.add(0,'some value');

什麼將是該操作的時間複雜度？

Java Doc沒有指定這個。

而且

我剛開始學習Java，我看到了一句

An ArrayList in Java is a List that is backed by an array.

什麼是 '支持' 在這裏是什麼意思？謝謝！

來源

2013-05-27 lakeskysea

這意味着'ArrayList'是一個實現，'List'是一個接口。 –

從某種意義上講，ArrayList在技術上只是一個數組。它使用System.arraycopy方法來處理添加和刪除元素。在這種情況下，它將創建兩個數組，一個來自0-0（空），另一個來自（0-n）。然後它創建一個長度爲+1的新數組，並將它們組合在一起，將新元素放入各自的索引處。 – 2013-05-27 17:25:31

將一個元素添加到數組的開頭是O（n） - 它需要將所有現有的元素移動一個位置。

數組列表中的所有元素都存儲在一個連續的數組中。如果添加比當前數組大小的元素 - 它將自動增長以適應新元素。

增加到最後是O（1）分攤多次插入。

來源

2013-05-27 17:27:23 gkamal

我知道O（n）是正常的情況，但我實際上是問Java是否在這種情況下做了一些魔術（像Louis Wasserman提到的任何東西）？對不起，不夠清楚！ – lakeskysea

你是什麼意思，「這個案子」？ –

@LouisWasserman抱歉，我的意思是'這個操作'。這個操作通常需要O（n），但我想知道Java的實現是否有一些'聰明的方式'在ArrayList的開頭添加元素。你能否詳細說明你的答案爲什麼需要線性時間？ – lakeskysea

ArrayList.add(0, element)需要線性時間，但這個常數很低，因爲它可以使用熾熱的快速System.arraycopy。

來源

2013-05-27 17:27:29

從零開始構建列表並添加大量元素到開始以二次方式運行：O（n ）。
將所有元素添加到列表末尾，然後調用 Collections.reverse(list)以線性時間運行：O（n）。

來源

2017-07-05 05:25:37 Roland

在ArrayList的開頭添加一個元素的時間複雜度是多少？

回答

相關問題