目次
文書の過去の版を表示しています。
コレクション ジェネリック クラス の性能比較
Dictionary<TKey, TValue>
処理 | 計算量 |
---|---|
メソッド | |
Add | Count ⇐ 容量 O(1)に近い Count > 容量 O(n) - 自動拡張の為 |
Clear | O(n) |
ContainsKey | O(1)に近い |
ContainsValue | O(n) |
Remove | O(1)に近い |
プロパティ | |
Count | O(1) |
Item | O(1)に近い |
HashSet<T>
処理 | 計算量 |
---|---|
メソッド | |
Add | Count ⇐ 容量 O(1)に近い Count > 容量 O(n) - 自動拡張の為 |
Clear | O(n) |
Contains | O(1) |
Remove | O(1) |
プロパティ | |
Count | O(1) |
LinkedList<T>
処理 | 計算量 |
---|---|
メソッド | |
AddAfter、AddBefore、AddFirst、AddLast | O(1) |
Clear | O(n) |
Contains | O(n) |
Find | O(n) |
FindLast | O(n) |
Remove | O(n) |
RemoveFirst、RemoveLast | O(1) |
プロパティ | |
Count、First、Last | O(1) |
List<T>
処理 | 計算量 |
---|---|
メソッド | |
Add | Count ⇐ 容量 O(1) Count > 容量 O(n) - 自動拡張の為 |
AddRange | Count ⇐ 容量 O(n) Count > 容量 O(n + m) - 自動拡張の為 |
Clear | O(n) |
Contains | O(n) |
Exists | O(n) |
Find、FindAll、FindIndex、FindIndex、FindLastIndex | O(n) |
GetRange | O(n) |
IndexOf | O(n) |
Insert | O(n) |
InsertRange | O(n + m) |
LastIndexOf | O(n) |
Remove、RemoveAll、RemoveAt、RemoveRange | O(n) |
Reverse | O(n) |
Sort | O(n log n) |
プロパティ | |
Count | O(1) |
Item | O(1) |
Queue<T>
処理 | 計算量 |
---|---|
メソッド | |
プロパティ | |
SortedDictionary<TKey,TValue>
処理 | 計算量 |
---|---|
メソッド | |
プロパティ | |
SortedList<TKey,TValue>
処理 | 計算量 |
---|---|
メソッド | |
プロパティ | |
Count | O(1) |
Item | 取得: O(log n) 設定(キー存在): O(log n) 設定(キー未存在):O(n) 追加: O(log n) Count > 容量 追加: O(n) |
Stack<T>
処理 | 計算量 |
---|---|
メソッド | |
プロパティ | |
O-記法と計算量/速度の関係
速度 | 高速 | < | 低速 | ||
---|---|---|---|---|---|
計算量 | 少ない | < | 多い | ||
記法 | O(1) | O(log n) | O(n) | O(n log n) | O(n2) |
名称 | 定数関数 | 対数 | 線形関数 | 準線形、線形対数 | 二乗関数 |
O-記法については ランダウの記号 - Wikipedia を参照のこと。