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)である。