アルゴリズムの超おおざっぱなメモ

探索木

• 幅優先探索：キュー(FIFO)
• 深さ優先探索：スタック(LIFO)
• 順位優先探索：ヒープ（順序付きキューでも可）

二分木

• 二分木：子はたかだか２つ
• 二分探索木：子はたかだか２つ、左子<親<右子
• 完全二分木：子はたかだか２つ、かつ偏りがない
• ヒープ木：完全二分木、かつ頂点は最小値

クラスの話

• P：決定性（deterministic）アルゴリズムを使って多項式（Polynomial）時間で解ける問題
• NP：非決定性（Nondeterministic）アルゴリズムでうまくいくと多項式（Polynomial）時間で解ける問題
判定問題
• NP困難：多項式時間で解けない
巡回セールスマン問題(TSP)とか、いわゆる最適化問題
• NP完全（難しいかどうかわからない問題）：NP困難でNPに属しているもの
論理式の充足可能性問題(SAT)とか

Algolithm noteてゆうサイトがいい感じだった