爲什麼ArrayList add（）和add（int index，E）的複雜度是攤銷常量時間？爲什麼不是O（1）爲add（），O（n）爲add（int index，E）？

Question

爲什麼ArrayList add（）和add（int index，E）複雜度是攤銷常量時間？ （1）對於單個add（）操作，O（n）對於單個add（int index，E）操作和O（n）用於添加n個元素（n個添加操作）添加方法？假設我們使用add（int index，E）很少添加到數組結尾？

是不是陣列（和ArrayList）已經具有n個元素的一個操作的複雜性：

1. 加（） - O（1）？
2. add（int index，E） - O（n）？

如果我們做一百萬插入，1和2的平均值不能是O（1），對不對？

爲什麼Oracle說

增加操作運行在分期常量時間，即，加入正 元件需要O（n）的時間。

我認爲對於add（）和O（n）來說add（int index，E）的複雜度是O（1）。

這是否意味着「n操作的整體複雜度」（複雜度O（1）的每個操作）可以說是n * O（1）= O（n）。我錯過了什麼？

也許對於Oracle「添加操作」總是意味着只添加（）？並添加（int，E）是「插入操作」？然後完全清楚！

我有一個猜想，它與漸近分析和攤銷分析之間的區別做的，但我不能把握到最後。

What is amortized analysis of algorithms?

Why the time complexity of an array insertion is O(n) and not O(n+1)?

More appropriate to say Amortized O(1) vs O(n) for insertion into unsorted dynamic array?（不是很清楚）

Big O when adding together different routines

Answer 1

在甲骨文方面（這是默認暗示），並談到列表

• 「add方法 「（同義詞 - 」 append方法 「）總是意味着boolean add(E)
• 」 插入方法「總是意味着boolean add(int index, E)

當甲骨文寫入

添加操作在運行攤銷不變的時間，也就是說，添加n元素需要O（n）時間。

它意味着：

單個boolean add(E)操作的複雜度是攤銷O（1）。

它不能只是O（1）漸近（總是），因爲很少需要增加數組容量。這種單一的添加操作其實是一個「創建新的更大的數組，將舊數組複製到其中，然後將一個元素添加到最後」的操作是O（n）漸近的複雜性，因爲在增加List容量時複製數組爲O n），生長加相加的複雜度爲O（n）[按O（n）+ O（1）= O（n）計算）。沒有這種容量增長操作，增加複雜性將會是O（1），元素總是被添加（附加）到數組的末尾（最大索引）。如果我們「添加」（=插入）而不是數組結束，我們需要移動最右邊的元素（具有更大的索引），並且單個這樣的操作的複雜度將是O（n）。現在，對於單個添加操作，漸近複雜度是O（1），而不是增加容量，O（n）是增加容量（這種情況非常少見）。

單次添加操作的攤銷複雜度爲O（1）。它反映了罕見的O（n）增長和增加操作被更多的O（1）增加不增長的操作所「稀釋」的事實，所以「平均」單個操作是O（1）。

n個加法運算的「漸近複雜度」是O（n）。但是在這裏我們談論n個操作的複雜性，而不是一個操作的複雜性。這並不是一個嚴格的方式（「漸近複雜性」），但無論如何。 n次操作的攤銷複雜性更不合理。

最後，boolean add(int index, E)單操作複雜度總是O（n）。如果觸發增長，則爲O（n）+ O（n）[增長+插入]，但2 * O（n）與O（n）相同。