在arrayList的某個索引處插入元素的運行時間是多少？

我想知道什麼是add(index,E)方法java ArrayList的運行時間。根據javadoc添加操作的運行時間分攤到O(1)。但在add(index,E)的說明中就是這樣說的。在arrayList的某個索引處插入元素的運行時間是多少？

將指定的元素插入此列表中的指定位置。將當前位於該位置的元素（如果有）和任何後續元素向右移（將其中的一個添加到其索引）。

所以它看起來像O(N)。我想知道我們需要交易什麼，如果這個操作的運行時間是O(1)。是否有任何攤銷工作可以完成此操作並犧牲其他操作的運行時間？

我讀過，java ArrayList是由數組支持的，會改變數據結構的幫助嗎？

來源

2013-06-20 tejas

[定期添加]（http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html#add（E））被攤銷O（1），[add at index ]（http://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html#add%28int,%20E%29）已分期付款O（N） –

ArrayList對於添加/刪除的任意索引具有O（n）時間複雜度，但O（1）用於列表末尾的操作。 Closer到O（1）查找意味着可能是像Hash Table支持的數據結構索引作爲鍵和元素作爲值。再次插入將花費O（n）時間，因爲它會觸發調整大小。

來源

2013-06-20 05:22:51 NINCOMPOOP

對於哪個查找操作'O（1）'你指的是時間嗎？ – jason

你是說當你說查找時加上？ – tejas

一個天真的數組支持列表實現將複製每個項目作爲一個單獨的操作插入一個插入。幸運的是，要移動的字節在內存中都是連續的，每個操作系統都支持在單個快速操作中有效地複製大塊內存。

因此，插入陣列中間並不像您想象的那麼糟糕。當然，如果您的應用程序具有正確的訪問模式，將數據結構更改爲鏈接列表可能會更快。

來源

2013-06-20 05:24:57 Rob

如何將數據結構更改爲鏈接列表幫助？如果O（1）同意，插入鏈表中，但找到插入的位置可能需要O（N），那麼這不會破壞我們的目的嗎？ – tejas

因此，警告「如果你的應用程序有正確的訪問模式。」例如，如果您沿着列表行進並根據您在其中找到的內容決定將項目插入當前位置或其附近，那麼鏈接列表的效果很好。如果你需要完全隨機訪問，那麼鏈表就很糟糕。 – Rob

鏈接列表與數組的另一個方面是調整大小。由於調整大小，Java實現了分段O（1）用於添加操作。 – tejas

在arrayList的某個索引處插入元素的運行時間是多少？

回答

相關問題