アルゴリズム・データ構造
| タスク | 手法 | 手法 | 必要な計算量 | 必要な計算量 |
|---|---|---|---|---|
| 最大公約数 | 両者の余りが0になる最大公約数を地道に探す方法 | $\mathcal{O(n)}$ | ||
| ユークリッドの互除法 | $\mathcal{ O(logn)}$ | ----- | ||
| ソート | 選択ソート | $\mathcal{O(n^2)}$ | ----- | |
| マージソート | $\mathcal{O(nlogn)}$ | ----- | ||
| クイックソート | $\mathcal{O(nlogn)}$ | 入力配列がソートされていると $\mathcal{O(n^2)}$ | ||
| データ探索 | 線形探索 | $\mathcal{O(n)}$ | ----- | |
| 二分探索 | $\mathcal{O(nlogn)}$ | ----- | ||
| 二分探索木 | 平衡木 | $\mathcal{O(logn)}$ | ソート $\mathcal{O(n)}$ | |
| ヒープ | 最小値を取り出す | $\mathcal{O(1)}$ | ||
| 更新 | $\mathcal{O(logn)}$ | |||
| 作成 | $\mathcal{O(n)}$ | |||
| ヒープソート | $\mathcal{O(nlogn)}$ | |||
| ハッシュテーブルの探索 | $\mathcal{O(1)}$ | |||
| 要素の除去 | pythonのリスト | dequeの方が効率的 | $\mathcal{O(n)}$ |
グラフ構造
| タスク | 手法 | 手法 | 必要な計算量 | 必要な計算量 |
|---|---|---|---|---|
| 探索 | 幅優先探索 | |||
| 探索 | 幅優先探索 | |||
| 最短距離計算 | ダイクストラ法 |