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:

The best resource is straight from the official API:

size、isEmpty、get、set、iterator 和 listIterator 操作以恒定时间运行.add 操作在分摊常数时间内运行，即添加 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屋！