webdevqa.jp.net

Java ArrayListの時間の複雑さ

特定の方法を扱ったこの質問の他のエントリを見つけましたが、包括的なものはありませんでした。このデータ構造で最も頻繁に使用される方法について、自分の理解を確認したいと思います。

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)

これは正しいです?ご協力いただきありがとうございます。

24
dvanaria

最良のリソースは 公式API から直接です:

サイズ、isEmpty、get、set、iterator、およびlistIterator操作は、一定の時間で実行されます。追加操作は償却された一定時間で実行されます。つまり、n個の要素を追加するにはO(n)時間が必要です。他のすべての操作は線形時間で実行されます。 LinkedList実装の場合と比較して。

31
brian_d