Java ArrayList 的时间复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6540511/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Time Complexity for Java ArrayList
提问by dvanaria
I found other entries for this question that dealt with specific methods, but nothing comprehensive. I'd like to verify my own understanding of the most often used methods of this data structure:
我发现这个问题的其他条目涉及特定方法，但没有全面。我想验证一下我自己对这个数据结构最常用的方法的理解：
O(1) - Constant Time:
O(1) - 恒定时间：
isEmpty()
add(x)
add(x, i)
set(x, i)
size()
get(i)
remove(i)
O(N) - Linear Time:
O(N) - 线性时间：
indexof(x)
clear()
remove(x)
remove(i)
Is this correct? Thanks for your help.
这样对吗？谢谢你的帮助。
采纳答案by brian_d
The best resource is straight from the official API:
最好的资源直接来自官方 API：
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.
size、isEmpty、get、set、iterator 和 listIterator 操作在恒定时间内运行。add 操作在分摊常数时间内运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都在线性时间内运行（粗略地说）。与 LinkedList 实现相比，常量因子较低。
