概要
コーディングクイズを解く日課を再開するに当たって、リハビリを兼ねてアルゴリズムとデータ構造の基本について復習。
配列
- 連続した配置でメモリを確保する
- 単一のデータ型
- サイズは一般的には固定だが、言語によっては動的（可変長配列）
- サブアレイ
- サブシーケンス
- 要素順を変更せずに、一部の要素が削除された形で取り出される配列
- サブアレイもサブシーケンスになり得る
時間計算量
| 操作 |
計算量 |
| アクセス |
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 {
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)) |
トライ
時間計算量
mは文字列の長さとする。
| 操作 |
計算量 |
| 検索 |
O(m) |
| 挿入 |
O(m) |
| 削除 |
O(m) |
参考
その他
データ構造とアルゴリズムの勉強に当たって参考にした記事。