モチベーション
この本👇
を読んでいると、間違いなく必要な知識のリストというのが出てきたので、それらについて知らないことは勉強して自分なりにまとめておきたい。
間違いなく必要な知識
これらを順にまとめていこう！
データ構造
連結リスト
JavaでいうところのLinkedList。Nodeが次の要素へのポインタを持っているような構造。
- 単方向(次の要素のポインタだけ)
- 双方向(前の要素のポインタも持つ)
の2種類があり、また
- 線形リスト
- 循環リスト
となっている場合もある。 index指定で要素を取得するのはメモリを連続的に確保している配列に比べると遅い。先頭への要素追加は配列のようにその他の要素をコピーしなくていいので爆速。ポインタを付けかえるだけなので基本的に追加削除が得意。 LinkedListの要素の追加は、追加する前(後)のNodeまでは先頭か最後尾からたどっていく必要はあり、その分の時間はかかる。
JavaのLinkedListの指定したindexのNodeを取得するメソッド👇前半か後半かを判断して先頭と最後尾のどちらから辿れば速いか判断して探してる。
木、トライ木、グラフ
木
連結(どの2点もつながっている)であり閉路(始点と終点が同じとなる経路)をもたないグラフ。ノードとエッジで構成される。
- root node 親をもたないノード
- leaf node 子をもたないノード
- internal node 子をもつノード
- height あるノードから葉ノードへのエッジ数の最大値。root nodeのheightはその木構造の高さ。
- depth あるノードからroot nodeまでのエッジ数のこと。root nodeは0。
トライ木
複数の文字列を保持するのに適したデータ構造。文字列の検索が高速。n文字の文字列の検索、挿入ともに で可能。辞書の実装などに使われている。
複雑なデータ構造や浮動小数点数などをトライ木で扱うには工夫が必要。少数の非常に長い文字列を格納する場合はメモリ効率が悪くなる。この場合はパトリシア木が適する。
グラフ
木やトライ木などを含む概念。ノードとエッジで構成されたもの。奥が深すぎるので一旦概念だけにしておこう。。。
スタックとキュー
スタック
いわゆる後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）ってやつ。割り込み処理などで使われる。
キュー
先入れ先出しのやつ。
ヒープ
挿入、削除がO(log n)で可能。探索はO(n)。 ルートが常に最小（または最大）要素となっているので、ルートの削除を繰り返すことで、ソートを行うことができる。 このときの計算量はO(n log n)。(ヒープソート)
なるほどなぁ
ベクタ/配列リスト
これはいいか。
ハッシュテーブル
これもよく使うけど一応。
ハッシュテーブル (英: hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。 (Wikipedia)
検索や追加が で可能。ただし、ハッシュ値が衝突した場合は、最悪の場合
となる。
衝突の対策として、オープンアドレス法とチェイン法がある
オープンアドレス
衝突したら、空いているアドレスに入れればよくね？という発送。新たに空いているアドレスを調べる方法はいろいろあるが、とにかく何らかの方法で空いているところを探す。例えば、もし衝突したら、隣のアドレスを見る、といった方法でもよい。この場合、その要素にはキー&バリューを保存しておき、探索の際はハッシュ値によって特定したアドレスから順に要素（キー）を見て、お目当ての要素を探す。
チェイン
ハッシュ関数で導いたアドレスに、連結リストの先頭Nodeを入れておく。衝突した場合はそのリストの先頭に要素を追加していく。 探索の際は、ハッシュ関数で連結リストを特定し、そこから全要素を調べる。リストの要素にはキーも格納されているので、それを見て探索する。
アルゴリズム
幅優先探索
ツリー構造で使うアルゴリズム。言葉のまま。
function 幅優先探索(v)
Q ← 空のキュー
v に訪問済みの印を付ける
v を Q に追加
while Q が空ではない do
v ← Q から取り出す
v を処理する
for each v に接続している頂点 i do
if i が未訪問 then
i に訪問済みの印を付ける
i を Q に追加
深さ優先探索
function 深さ優先探索(v)
v に訪問済みの印を付ける
v を処理する
for each v に接続している頂点 i do
if i が未訪問 then
深さ優先探索(i)
二分木
アルゴリズムの欄に二分木と書いてあってよくわからない（二分木はデータ構造のはず）のだけど、とりあえずデータ構造についてメモ。 二分木はedgeの数が2本以下の木構造。全部edgeが2本あったら全二分木、深さが全て同じなら完全二分木。二分木を走査するアルゴリズムとして👆の幅優先探索や深さ優先探索がある。
二分探索木はWikipediaによれば
構造は二分木と同じだが、「左の子孫の値 ≤ 親 ≤ 右の子孫の値」という制約を持つ。左の子孫の値と右の子孫の値の両方に等号をつけているが、実際にはどちらかに統一しておく必要がある。
という感じ。「子」じゃなくて「子孫」ってのがポイントやね
マージソート
分割統治法にてソートする方法で、再帰的に二分し分解していき、2要素以下になったらソート->マージを繰り返す方法。
クイックソート
これも分割統治法の一種で、基準を決めてその基準より大きい<->小さいに分ける。それぞれのブロックについても再帰的にやっていく。計算量は 。最悪の場合は
。
概念
ビット操作
この記事でまとめた👇 naotech.hatenablog.com
メモリ（スタック vs. ヒープ）
スタック
OSやコンパイラが割当を行う領域で、プログラムから自由に確保はできない。関数の情報や、変数などをこの領域に保持する。例えば
main() {
test();
}
test() {
const a = 1;
}
とした場合は、main -> test -> a と順番にスタック領域に情報が積まれていって、使われなくなる順に沿って（つまり積まれたのとは逆順に） a -> test -> main とメモリから消えていく。 ソースコードを見て静的にどこのメモリを使えばいいか判断できるから、コンパイラがやってくれるんですね。メモリの管理方法としては、とびとびになったりしないので、高速なようです。
ヒープ
heap。英語で「積み重ね、山」という意味らしい。ヒープというデータ構造もまぁそれっぽいっちゃそれっぽいすね。 動的にプログラムから確保できる領域。例えば、ファイルをプログラムで読み込んでそれをメモリに乗せる場合、その容量がどれくらいかは分からないのでコンパイル時点では確保できませんね？つまりスタックには乗せられません。こういったものはヒープに乗せます。とりあえず動的にその都度必要なものを無計画に積んでいく様とheapという言葉はつながるものがありますね。 実際にheap領域をどう扱うかの実装はものによって違うので、実装が実際にヒープ構造になっているかどうかとかはあまり気にしなくて良さそう。
ガベージコレクションはこのヒープ領域の要らなくなったメモリを勝手に破棄してくれる仕組みです。
再帰
- 自分を呼び出せば再帰
- ベースケースの処理を入れて再帰をとめないとだめ
- 再帰するときの途中までの結果をメモリに積んでおいて高速に処理する方法がメモ化再帰
- n個に対する課題をn-1個に対する課題に帰着できれば、再帰で実装できそう
- 部分和問題(n個のうち合計がXになる組み合わせを探す)については、1つ目の値Aを使う場合は、残りn-1個でX-Aの値を作れるかどうか、1つ目の値Aを使わない場合は残りn-1個でXを作れるかどうか、という話に帰着できるので再帰が使える
動的計画法
Wikipediaによれば
対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。
らしいです。この具体例がメモ化再帰ですね。
ビッグ・オー記法、スペース
これはこの本でも何回も出てきてますが、再度自分の言葉でまとめよう。以下はとりあえず学術的な定義。
ビッグ・オー記法
実際にかかる時間の上限であればいい。それより計算量が大きくなることはない、って意味合い。例えば配列の各要素を出力するのは だけど、ビッグ・オー記法で書け、と言われたら
でも間違いじゃない。意味ないけどな。
ビッグ・オメガ記法
オーと違いこいつは下限であればいい。それより計算量が小さくなることはない、って意味合い。配列の各要素出力の例で言えば、 でもいい。意味ないけどな。
ビッグ・シータ記法
と
の両方の意味、すなわち
かつ
のときに
と言える。
面接では
ただしコーディング面接でのO記法はΘの意味合いに近く、あるアルゴリズムでありえる最悪の計算量をOを使って表すのが正しいとされている。つまり、各要素を出力するのは だと間違いで、
って答えないとだめ。
スペース
空間計算量のことかな。
