Java ArrayList的时间复杂度 [英] Time Complexity for Java ArrayList
问题描述
我发现这个问题的其他条目涉及具体的方法,但没有什么全面的。我想验证自己对这种数据结构最常用的方法的理解:
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) - 常数时间:
O(1) - Constant Time:
isEmpty()
add(x)
add(x, i)
set(x, i)
size()
get(i)
remove(i)
O(N) - 线性时间:
O(N) - Linear Time:
indexof(x)
clear()
remove(x)
remove(i)
这是正确的吗?感谢您的帮助。
Is this correct? Thanks for your help.
推荐答案
最好的资源是直接从官方API :
大小,isEmpty,get,set,iterator和listIterator操作在常量运行。添加操作以摊余常数运行,即添加n个元素需要O(n)个时间。所有其他操作都以线性时间运行(粗略地说)。与LinkedList实现相比,常数因子较低。
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.
这篇关于Java ArrayList的时间复杂度的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!