参考リソース
データ構造操作の複雑度早見表
| データ構造 | 挿入 | 削除 | 検索 | 走査 |
|---|---|---|---|---|
| 配列 | O(n) 中間 / O(1) 末尾 | O(n) 中間 / O(1) 末尾 | O(1) インデックス / O(n) 値 | O(n) |
| 単方向リスト | O(1) 先頭 / O(n) 末尾 | O(1) 先頭 / O(n) 指定位置 | O(n) | O(n) |
| 双方向リスト | O(1)（位置が既知の場合） | O(1)（位置が既知の場合） | O(n) | O(n) |
| 栈 | O(1) | O(1) | — | — |
| キュー | O(1) | O(1) | — | — |
| 優先度付きキュー（ヒープ） | O(log n) | O(log n) | — | — |
| 二分探索木（BST） | O(log n)~O(n) | O(log n)~O(n) | O(log n)~O(n) | O(n) |
| ハッシュテーブル | O(1) 平均 | O(1) 平均 | O(1) 平均 | — |
| 堆 | O(log n) | O(log n) | O(1) ヒープの先頭 | — |
| 图 | O(1) 隣接リスト | O(E) | O(V+E) DFS/BFS | O(V+E) |
ソートアルゴリズム早見表
| アルゴリズム | 平均複雑度 | 最悪複雑度 | 空間 | 安定 | 一言で言うと |
|---|---|---|---|---|---|
| バブル | O(n²) | O(n²) | O(1) | である | シンプルだが遅い、教育向き |
| 選択 | O(n²) | O(n²) | O(1) | 否 | 交換回数が最小 |
| 挿入 | O(n²) | O(n²) | O(1) | である | 小規模またはほぼ整列済みの場合に最適 |
| クイック | O(n log n) | O(n²) | O(log n) | 否 | 汎用の第一選択、パーティションの考え方が巧妙 |
| マージ | O(n log n) | O(n log n) | O(n) | である | 性能は安定しているが余分なスペースが必要 |
| ヒープ | O(n log n) | O(n log n) | O(1) | 否 | インプレースソートで空間効率が最良 |
| シェル | O(n^1.3) | O(n²) | O(1) | 否 | 挿入ソートの改良版 |
ビッグオー複雑度ランキング
| 複雑度 | n=10 | n=1000 | n=1000000 | 評価 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 最良 |
| O(log n) | ~3 | ~10 | ~20 | 極めて良好 |
| O(n) | 10 | 1000 | 1000000 | 許容可能 |
| O(n log n) | ~30 | ~10000 | ~20000000 | まずまず |
| O(n²) | 100 | 1000000 | 10¹² | 注意が必要 |
| O(2ⁿ) | 1024 | 天文学的な数字 | 不可能 | 使えない |
おすすめ学習リソース
| カテゴリ | 名称 | 説明 |
|---|---|---|
| 定番教科書 | 『データ構造（C言語版）』嚴蔚敏 | 国内大学の標準的な教科書で、体系が整っている |
| 定番教科書 | 『アルゴリズムイントロダクション』(CLRS) | アルゴリズム分野の権威ある参考書で、深く体系的 |
| オンライン演習 | LeetCode (leetcode.com) | 大量のアルゴリズム問題、面接対策の第一選択 |
| オンライン演習 | 牛客网 (nowcoder.com) | 国内の面接練習プラットフォーム、新卒採用準備に最適 |
| 可視化ツール | Visualgo (visualgo.net) | アルゴリズムの可視化、実行プロセスの理解を助ける |
| オンラインコンパイラ | Compiler Explorer (godbolt.org) | Cコードのコンパイル後のアセンブリを確認し、低レベルを理解する |