首页 ❯

Java ArrayList 的时间复杂性

arrays data-structures java arraylist abstract-data-type
2022-09-01 12:05:09

我发现这个问题的其他条目涉及具体方法，但没有全面的内容。我想验证我自己对这种数据结构最常用的方法的理解：

O（1） - 恒定时间：

isEmpty()
add(x)
add(x, i)
set(x, i)
size()
get(i)
remove(i)

O（N） - 线性时间：

indexof(x)
clear()
remove(x)
remove(i)

这是正确的吗？感谢您的帮助。


答案 1

最好的资源直接来自官方API：

大小、isEmpty、get、set、迭代器和 listIterator 操作在恒定时间内运行。添加操作在摊销常量时间内运行，即添加 n 个元素需要 O（n） 时间。所有其他操作都在线性时间中运行（粗略地说）。与LinkedList实现相比，常数因子较低。


答案 2

推荐
更多 »
标签
更多 »
php pass-by-reference optional-parameters default-value javascript arrays dom function string object serialization tostring visibility syntax jslint use-strict operators equality equality-operator identity-operator datetime timestamp date-arithmetic redirect angularjs loops foreach iteration scope variables
推荐
更多 »