概要
コーディングクイズを解く日課を再開するに当たって、リハビリを兼ねてアルゴリズムとデータ構造の基本について復習。
配列
- 連続した配置でメモリを確保する
- 単一のデータ型
- サイズは一般的には固定だが、言語によっては動的（可変長配列）
- サブアレイ
- 配列内から連続した形で取り出される配列
- [1, 2, 3, 4, 5]
- →[2, 3, 4]
- [1, 2, 3, 4, 5]
- 配列内から連続した形で取り出される配列
- サブシーケンス
- 要素順を変更せずに、一部の要素が削除された形で取り出される配列
- [1, 2, 3, 4, 5]
- →[1, 3, 4]
- [1, 2, 3, 4, 5]
- サブアレイもサブシーケンスになり得る
- 要素順を変更せずに、一部の要素が削除された形で取り出される配列
時間計算量
| 操作 | 計算量 |
|---|---|
| アクセス | O(1) |
| 検索 | O(n) |
| 検索（ソート済み） | O(log(n)) |
| 挿入 | O(n) |
| 挿入（末尾） | O(1) |
| 削除 | O(n) |
| 削除（末尾） | O(1) |
考慮事項
- 配列内の重複の扱いをどうするか？
- インデックスによるアクセスで範囲外にならないように気をつける
文字列
- 言語によって、配列であったり、可変長配列であったり、オブジェクトであったりする
- 文字列検索のための一般的な木構造
- トライ木（プレフィックス木）
- サフィックスツリー
時間計算量
実装によるので割愛
考慮事項
- 大文字・小文字の区別
- ASCII Tableを利用できないか？
ハッシュテーブル（ハッシュマップ）
- 連想配列
- キーを値にマップした構造
| 操作 | 計算量 |
|---|---|
| アクセス | N/A |
| 検索 | O(1)※ |
| 挿入 | O(1)※ |
| 削除 | O(1)※ |
※平均ケース
考慮事項
- ハッシュが衝突する可能性があるか？
再帰
- 関数内で関数自身を呼び出す処理
時間計算量
実装によるので割愛
考慮事項
- 再帰の終了条件を定義すること
- 深すぎる再帰処理はスタックオーバーフローに気をつける
- 末尾呼び出し最適化（TCO：Tail Call Optimization）がサポートされている言語だと回避しやすい
ソートと探索
ソートアルゴリズムの計算量
| アルゴリズム | 時間計算量 | 空間計算量 |
|---|---|---|
| バブルソート | O(n^2) | O(1) |
| 挿入ソート | O(n^2) | 0(1) |
| 選択ソート | O(n^2) | O(1) |
| クイックソート | O(nlog(n)) | O(log(n)) |
| マージソート | O(nlog(n)) | O(n) |
| ヒープソート | O(nlog(n)) | O(1) |
| カウントソート | O(n+k) | O(k) |
| 基数ソート | O(nk) | O(n+k) |
探索アルゴリズムの計算量
| アルゴリズム | 計算量 |
|---|---|
| 二分探索 | O(log(n)) |
二次元配列
- 配列が配列を持った構造
- 数学でいうベクトルや行列に近い概念
- 1次元配列はliner array、多次元配列はmultidimentional arrayという
package main
import "fmt"
func main() {
matrix := [][]int{[]int{0, 1}, []int{2, 3}, []int{4, 5}}
for i, v := range matrix {
for j, _ := range v {
// iがrowでjがcolumn
matrix[i][j] = 0
}
}
fmt.Println(matrix)
}
考慮事項
- 空の行や列が存在するか？ 長さが0の配列があるか？
- 何次元が必要か？
連結リスト
- 各データが次のデータへのリンク（またはポインタ）を持った順次的なデータ構造
- データ挿入がO(1)
- データ削除は位置が指定されている場合に限りO(1)
- データへのアクセスは線形になる
- 片方向リスト
- 各データが次のデータへの参照だけ持つ
- 双方向リスト
- 各データが前後の参照を持つ
- 循環リスト
- 最後のデータが最初のデータへの参照を持つ
時間計算量
| 操作 | 計算量 |
|---|---|
| アクセス | O(n) |
| 検索 | O(n) |
| 挿入 | O(1) |
| 削除 | O(1) |
キュー
- 一般的にFIFOのリスト構造で保持されるデータ構造
- 待ち行列
- エンキュー
- キューの追加
- デキュー
- キューの取り出し
時間計算量
| 操作 | 計算量 |
|---|---|
| エンキュー | O(1) |
| デキュー | O(1) |
スタック
- LIFOまたはFIFOの構造で保持されるデータ構造
- プッシュ
- データの追加
- ポップ
- データの取り出し
時間計算量
| 操作 | 計算量 |
|---|---|
| プッシュ | O(1) |
| ポップ | O(1) |
木
- 階層構造を表すデータ構造
- 無向の非循環グラフ
- 二分探索木
グラフ
- ノード間の関係性を表したデータ構造
- 無向または有向
計算量
Vは頂点、Eはエッジの数とする。
| アルゴリズム | 計算量 |
|---|---|
| 深さ優先検索 | O(V+E) |
| 幅優先検索 | O(V+E) |
| トポロジカルソート | O(V+E) |
ヒープ
- 子が親より常に大きい（小さい）または等しいという制約を持つ木構造
時間計算量
| 操作 | 計算量 |
|---|---|
| 挿入 | O(log(n)) |
| 削除 | O(log(n)) |
トライ
- 文字列の検索と保存の効率に特化した木構造
- cf. Golangでトライ木を実装する
時間計算量
mは文字列の長さとする。
| 操作 | 計算量 |
|---|---|
| 検索 | O(m) |
| 挿入 | O(m) |
| 削除 | O(m) |
参考
その他
データ構造とアルゴリズムの勉強に当たって参考にした記事。
