Collectionインターフェイスの計算量

計算量

https://beta.atcoder.jp/contests/abc094/tasks/arc095_a

ArrayListから要素のindexをindexOf((Object)x)で検索するのが、ランダムアクセスであるget(i)と同じように、O(1)と勘違いしていた。TLEになるからなんでや、、 と思っていたので、java.util.Collectionを復習しておく。

クラス 要素の追加 要素の検索 要素の削除 ランダムアクセス
ArrayList O(n) O(n) O(n) O(1)
LinkedList O(1) O(n) O(1) O(n)
HashSet O(log n) O(log n) O(log n) 不可能
TreeSet O(log n) O(log n) O(log n) 不可能

上記の表の通り、ArrayListでの要素の検索の計算量はO(n)である。

参考

Computational Complexity, and How to use the Class library