More than 5 years have passed since last update.

アルゴリズムとデータ構造

algorithm

Last updated at 2019-02-17Posted at 2019-01-31

アルゴリズムとデータ構造に関連した基礎知識をまとめておく。

英文で出てきた時に理解できることを目的に可能な限り英語表記を優先しているが、いくつかは日本語での表記も併記してある。ものによっては練習用にAOJの問題をリンクしてある。

1. アルゴリズム

Comparison Sort

何らかの方法で要素同士を比較できる配列に対して適用可能なソートアルゴリズムのことをComparison sortやComparison-based sorting algorithmという。

Bubble Sort

ALDS1_2_A: 最初は端から端に全てを比較して入れ替え、入れ替える幅を狭めながらその操作を繰り返す。

Time Complexity: $O(N^2)$
- 配列の流さが $n$ の時、$n-1$, $n-2$, ..., $1$ 回の比較・入れ替えを行なう。
- $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ なので、 $\sum_{k=1}^{n-1} k = \frac{n^2-n}{2}$ 回計算が必要
Space Complexity: $O(1)$
Stable Sort: Yes
- 離れた要素を直接交換しないため安定ソートになる
- 同じ要素が通り越さないよう、<= ではなく < で比較するよう気をつける

Selection Sort

ALDS1_2_B: 端から端まで探索し、最小値を見つけて入れ替えるのを範囲を狭めながら繰り返す。

Time Complexity: $O(N^2)$
- 比較演算の回数がデータに依存せず、計算量はバブルソートと同じ
Space Complexity: $O(1)$
Stable Sort: No
- 離れた要素をいきなり交換するため操作中順序が保証されず、安定ソートにならない

Insertion Sort

ALDS1_1_A: 2要素で比較しソート、隣りの1つを加え3要素でソート、というように徐々にソート済の範囲を増やしていく。

Time Complexity: $O(N^2)$
- 入力データが降順になっている場合の最悪計算量はバブルソートと同じ
- 入力データが昇順だった場合はおよそ$N$回の比較で済むため高速
Space Complexity: $O(1)$
Stable Sort: Yes
- 離れた要素を直接交換しないため安定ソートになる

Shell Sort

ALDS1_2_D: 一定の間隔離れた要素のみを対象としてInsertion Sortを行ない、その幅を任意の方法で増やして最後に普通のInsertion Sortをする

Time Complexity: $O(N^2)$
- $g = 1, 4, 13, ...$ のように $g_{n+1} = 3g_{n} + 1$ の数列を用いると $O(N^{1.25})$ になると予測されている
- $2^p = 1, 2, 4, ...$ のように2のべき乗を用いると、$g = 1$までにソートの対象にならない要素が多く発生してしまい、効率化が期待できない
Space Complexity: $O(1)$
Stable Sort: No
- 一定間隔離れた要素の交換を行なっているので、安定ソートにならない

Quick Sort

ALDS1_6_C: ある値をピボットに選びパーティションを行なう操作を再帰的に繰り返す。パーティションは、対象範囲の中でピボットより小さい値を入れておく範囲の最後のインデックスを用意し、ピボットより小さい値を見つけたらそのインデックスの1つ右と入れ替えるという操作を繰り返して行なう。

Time Complexity: 最良または平均で $O(N\log_2 N)$
- およそ$log_2N$の階層ができ、各階層の要素の合計は$N$となるため。
- 最悪計算量が$O(N^2)$: 端の値をピボットに選び続けるとソート済の値などで$N$個の階層ができ最悪計算量が$O(N^2)$となってしまうため。
- ピボットをランダムに選んだり、適当に3つ程度選んだ値の中央値を使うなど工夫する必要がある。
Space Complexity: $O(1)$
- 上記のようにインプレースでパーティションを実装することができるため。単純な実装では$O(N)$になる。
Stable Sort: No
- パーティション時に離れた値を交換するので安定ソートにならない。

Quick Sortは一般に最も高速なソートアルゴリズムとして知られているが、C++で使われているIntro SortはQucik Sort, Heap Sort, Insertion Sortを組合せたアルゴリズムになっている。

Merge Sort

ALDS1_5_B: 対象範囲を半分に分割し、再帰的に左右をMerge Sortした後、それらの結果をマージする。マージの際に一時的にマージ対象の配列をコピーするので一時的なメモリを必要とする。

Time Complexity: $O(Nlog_2 N)$
Space Complexity: $O(N)$
Stable Sort: Yes
- 再帰の一番深いところで隣り合った要素同士を比較しており、隣り合っていない未ソートの離れた要素同士を交換しないので安定ソートになる。

Heap Sort

ALDS1_9_B: 最初に整列対象全体を後述のBinary Heapに変形し、その後最大値を取り出して一番後ろの領域にソート済の列として詰めていくのを繰り返す。
配列をBinary Heapに変形する際は、一番低いレベルの部分木からMax Heapになるよう親子関係を整理し、再帰的にrootまで繰り返すと木全体がMax Heapになる。

Time Complexity: $O(Nlog_2N)$
- $N$要素の配列のBinary Heap化: $N \sum_{k=1}^{logN} \frac{k}{2^k} = O(N)$
  - 高さ1の部分木 N/2 個, 高さ2の部分木 N/4 個, ... に対して操作を行なうため
- Binary Heapからのextract max ($log_2N$)の$N$回繰り返し: $O(Nlog_2N)$
Space Complexity: $O(1)$
Stable Sort: No
- Binary Heapを構築した時点で遠い要素が直接交換され、安定ソートにならない

Distribution Sort

Comparison sortでないものをNon-comparison sortというが、その中でも入力を一時的なデータ構造に分配した後、それを再度集めることでソートするアルゴリズムのことをDistribution sortという。

Bucket Sort

ソート対象の取りうる値が$K$種類しかない時、$K$個のバケツを用意し、対象を走査してバケツに値を対応づけた後、ソートしたい順序に従ってバケツから値を取り出すと$N$要素の配列が$O(N+K)$でソートができるというもの。

可変長の要素を保持できるデータ構造をバケツにした場合、

Time Complexity: 最悪 $O(N^2)$, 平均 $O(N+K)$, 最良 $O(N)$
Space Complexity: 最悪 $O(NK)$
Stable Sort: Yes
- 素直にバケツにいれた順序で取り出せば安定ソートになる

Bucket Sortの別の実装方法としてCounting Sortがある:

Counting Sort

ALDS1_6_A: 計数ソート。取り得る値全ての出現回数を記録できる配列を用意し、リストを線形探索して各値の出現回数をカウントした後、そのカウント配列を元にリストを後ろから探索し直してソート後のインデックスを計算しセットしていく。

リストの長さをN、取り得る値が0以上K以下である時:

Time Complexity: 最悪 $O(N+K)$
Space Complexity: 最悪 $O(N)$
Stable Sort: Yes

Radix Sort

基数ソート。入力の数列に対して桁ごとにキーを分類し、それぞれの桁について下位のキーから安定ソートでソートするアルゴリズム。全体で$O(NK)$にするにはそのソートアルゴリズムは$O(N)$である必要があり、取り得る値の範囲が限られていることからそのソートにはBucket Sortを利用すると効率的になる。

桁数を$K$とした時、

Time Complexity: 最悪 $O(NK)$
Space Complexity: 最悪 $O(NK)$
Stable Sort: Yes

Sort: Graph

Topological Sort

閉路の無いDirected GraphのことをDAG (Directed Acyclic Graph) という。DAGの各辺について、出力元のnodeが必ず出力先のnodeの前に来るように並べること。

BFSかDFSを使うと比較的簡単に実装できる:
- BFS: 全てのnodeに入力次数を設定した後、入力次数が0のnodeだけキューに入れ、結果を入れるリストの最後にデキューしたnodeを追加しその出力先をエンキューする関数を再帰的に呼び出す。
- DFS: 全てのnodeをループし、チェック済みのnodeはスキップしながらループ内で再帰的に辺の出力先をvisitし、visit関数の最後で結果を入れるリストの先頭に追加する。
Time Complexity: $O(|V| + |E|)$
- 頂点の数V、辺の数EであるグラフG=(V, E)に関して、頂点の数を|V|、辺の数を|E|と表記する

Search: List

Linear Search

ALDS1_4_A: 先頭から順に比較を行なう。1つの要素を見つける場合、

Time Complexity: $O(N)$
Space Complexity: $O(1)$

Binary Search

ALDS1_4_B: 配列がソート済の場合に使える。中央の値を見て、検索したい値が左にあるか右にあるか判定するのを再帰的に繰り返す。

中央のインデックスを計算する際、オーバーフローしないように low + (high - low) / 2 のように中央の値を決定する必要がある点に注意。Nearly All Binary Searches and Mergesorts are Broken.

Time Complexity: $O(log_2 N)$
Space Complexity: $O(1)$

Search: Tree, Graph

BFS: Breadth First Search

ALDS1_11_C: 幅優先探索。より早く到達した階層を先に探索するため、First In First Outであるキューを用いて実装する。

A*

探索対象をキューに詰め、ヒューリスティック関数の結果が最小の物をデキューして探索するのを繰り返す。通常はPriority Queueを使う。後述のDijkstra's Algorithmを推定値付きの場合に一般化したアルゴリズムであると解釈でき、Dijkstra's Algorithmと同様にヒューリスティック関数が負の値を返すと完全性を失う。

なおA*という名前になっているのは、A*アルゴリズムが最初に発表された論文においてAdmissible(許容的)な集合がAで表わされ、その中で評価回数が最適になるものをA*と表記したため。

DFS: Depth First Search

ALDS1_11_B: 深さ優先探索。後の方に到達した階層を先に探索するため、Last In First Outであるスタックを用いて実装する。コールスタックもスタックとして使えるので、再帰関数を使って実装しても良い。

Depth-Limited Search

ある深さで探索を打ち切るDepth First SearchをDepth-Limited Search(深さ制限探索)という。

IDDFS: Iterative Deepening Depth-First Search

徐々に深さの制限を繰り返しながらDepth-Limited Searchを行なうことをIterative Deepening Depth-First Search(反復深化深さ優先探索)という。枝刈りをしない場合は実質BFSになるため、BFSで解けるような最適化問題を解くことが可能になる。BFSに比べメモリ消費量が小さくなりやすい。

IDA: Iterative Deepening A

Iterative Deepening DFSであり、探索中の状態に対する任意のヒューリスティック関数を用いて枝刈りを行なうアルゴリズムをIDA*と呼ぶ。ヒューリスティック関数によって返される値が大きいほどより多くの枝が刈られ高速になる(深さ制限に達しやすくなる)が、解を逃がす確率はその分大きくなる。

Search: String

Knuth-Morris-Pratt

部分マッチテーブルを生成しておき、その結果に応じて多くの文字をスキップすることにより高速に文字列を探索する。クヌース-モリス-プラット法

Time Complexity (文字列の長さk, パターンの長さn):
- テーブルが生成済の時: $O(k)$
- 毎回生成する場合: $O(k+n)$

Boyer-Moore

パターンを前処理してシフト規則のテーブルを生成し、その規則に従ってシフト処理を最後まで繰り返す。検索対象のテキストについては前処理を行なわないので、あるテキストについて何度も検索を行なわない場合に適している。ボイヤー-ムーア文字列検索アルゴリズム

Time Complexity (テキストの長さm, パターンの長さnの時):
- パターンがテキスト内に存在しない場合: 最悪 $O(n+m)$
- テキスト内に出現する場合: 最悪 $O(nm)$

Rabin-Karp

ローリングハッシュという、ある部分文字列のハッシュ値を計算した後、それを1つずらしたハッシュ値の計算が定数時間で可能なハッシュ関数を使って文字列を比較する。複数パターンの検索には効果的だが、1つのパターンの検索にはあまり用いられない。ラビン-カープ文字列検索アルゴリズム

Time Complexity (テキストの長さn, パターンの長さm):
- 最良および平均: $O(n)$
- まれに最悪: $O(nm)$
  - これがあるためあまり用いられない

Aho-Corasick

後述のTrieを利用して文字列探索を行なう。エイホ-コラシック法、Aho Corasick法

Time Complexityは、対象テキストの長さ、パターン群の長さ、見つかったマッチングの長さ全てに対して線形。

Minimum Spanning Tree

あるグラフにおいて全ての頂点を含む部分グラフの中で、Treeである(閉路を持たない)限りできるだけ多くの辺を持つものをSpanning Treeという。

重みつきグラフにおいて辺の重みの総和が最小のものをMinimum Spanning Treeという。

Kruskal's Algorithm

重みが最小の辺を削除し、Forestに加えていくのを繰り返す。貪欲法の一種。頂点がどの木に属しているかは後述のDisjoint-setデータ構造で判定する。クラスカル法

Time Complexity (グラフ内の辺数E, 頂点数V):
- $O(E log E)$ または $O(E log V)$

Prim's Algorithm

ALDS1_12_A, GRL_2_A: 任意の点を目的の木に含め、その木に接続されているがまだ木に含まれていない頂点を繋ぐ重み最小の辺を選んで目的の木に含めるのを繰り返す。計算量は、重みが最小の辺をどう探索するかで変わる。プリム法

Time Complexity (グラフ内の辺数E, 頂点数V):
- 単純な集合探索: $O(V^2)$
- Priority Queue (Binary Heap)とLinked List: $O(ElogV)$
- Priority Queue (Fibonacci Heap)とLinked List: $O(E + VlogV)$

Shortest Path Problem

ある重みつきグラフにおいて、与えられた頂点の組を経由する経路の中で辺の重みの総和が最小であるパスを求める問題。

Dijkstra's Algorithm

ALDS1_12_B, ALDS1_12_C: 最初にPriorityQueueに開始地点しかない状態で始め、到達コストが最小の頂点をPriorityQueueからデキューし、それに隣接する頂点のうちデキューした頂点から移動すると現時点で計算されている最小到達コストよりコストが小さくなる頂点をPriorityQueueに入れるという操作を繰り返す。ダイクストラ法、知れば天国、知らねば地獄――「探索」虎の巻

Time Complexity (グラフ内の辺数E, 頂点数V):
- オリジナル: $O(V^2)$
- Priority Queue (Binary Heap)とLinked List: $O((E+V)logV)$
- Priority Queue (Fibonacci Heap)とLinked List: $O(E + VlogV)$

Divide and Conquer

ALDS1_10_A: 分割統治法

大きな問題を小さな問題に分割して解く手法のこと。再帰関数で実装するとこれになる。

DP: Dynamic Programming

ALDS1_10_B, ALDS1_10_C, DPL_1_A, DPL_1_B: 動的計画法

普通に再帰関数を実装すると同じ小さな問題を複数回計算してしまうリスクがあるため、メモ化を利用して再計算を避ける手法。
メモ化再帰とも呼ばれる。
同じ種類の品物を1つまでしか入れられないKnapsack問題は0-1 Knapsack Problemと言われるが、これは動的計画法で効率的に解ける。

Math

Primality Test

ALDS1_1_C: 素数判定のアルゴリズムには、以下のようなものがある:

Trial Division: √N までの整数全てを順に割り切れるかどうか試す方法。$O(\sqrt{N})$になる。
- Prime Factorization (素因数分解) をする場合も、Nが小さければこれが使える。
Sieve of Eratosthenes: 素数列をあらかじめ用意したい場合、エラトステネスの篩を使うと与えられた範囲の全ての素数を高速に列挙できる。$O(log log N)$になる。

Greatest Common Divisor

ALDS1_1_B: 最大公約数を求めるには、Euclidian Algorithm (ユークリッドの互除法)を使う。

自然数 a, b (a >= b)について、r = a % bとすると、aとbの最大公約数はbとrの最大公約数に等しいという性質がある。
これを利用すると、a %= b と b %= a を交互に繰り返して剰余が0になった時の除数がaとbの最大公約数となる。
Time Complexity:
- 桁数($log_{10} N$)回の除算で最大公約数が求められるため、$O(log_{10} N)$
- このため、Trial Divisionで素因数分解するのに比べずっと速くなる。

2. データ構造

List

Stack

ALDS1_3_A: LIFO: Last In First Out.

Time Complexity
- push: $O(1)$
- pop: $O(1)$

Queue

ALDS1_3_B: FIFO: First In First Out. 待ち行列。

Time Complexity
- enqueue: $O(1)$
- dequeue: $O(1)$
  - 配列による実装では、リングバッファのように実装することで $O(N)$ なデータの移動を逐次行なうのを避ける

Linked List

ALDS1_3_C: 連結リスト。Singly-linked listとDoubly-linked listなどがある。

Time Complexity:
- insert into head: $O(1)$
- lookup: $O(N)$
- delete with key: $O(N)$

Hash Table

ALDS1_4_C: キーを元にしたハッシュ値を添字とした配列。要素数NのBucket Arrayを用意し、0〜N-1までの整数を生成するハッシュ関数を使う。

エントリの数nがNに近付くほど衝突の確率が高くなり性能が劣化し、n/Nをload factorという。速度劣化を回避するため、load factorが大きくなったらより大きいサイズの配列に入れ直す処理をrehashという。rehashには$O(N)$かかるが、配列のサイズを指数関数的に拡張するとAmortized Analysisで$O(1)$とみなせる。

ハッシュ値が衝突した場合の解決方法は主に以下の2つ:
- Separate chaining: ハッシュ値でアクセスされる配列をLinked Listの先頭としてハッシュ値が衝突している要素を全て格納し、そこから線形に探索する
- Open addressing: 衝突時にテーブル中の空いている別の番地を探す方式。ハッシュ値で示されるslotに何らかの方法で算出したprobe sequenceを加えた空いている場所に要素を挿入する。データ局所性により性能が向上するが、Bucket Arrayのサイズを越えて要素を格納できないので、rehashの回数が増えるリスクがある。
  - Linear probing: probe間に固定のinterval(通常は1)を使う
  - Quadratic probing: 元のハッシュ値を使った2次多項式でprobeを計算する
  - Double hashing: 2つ目のハッシュ値を計算する
Time Complexity:
- insert, lookup: 衝突しなければ $O(1)$, 頻繁に衝突する場合最悪 $O(N)$

シンボルテーブルの他、Bloom Filter(要素が集合のメンバーであるかテストができる、false positiveはあるがfalse negativeがないデータ構造)などにも利用される。

Tree

Binary Tree

ALDS1_7_B, ALDS1_7_C: 二分木。1つのrootを持ち全てのnodeについて子の数が2以下である木をBinary Treeという。

leaf: 子を持たないnode
internal node: leafではないnode
degree: あるnodeの子の数
depth: rootからあるnodeに至る経路のnode数。rootのdepthは0。
height: leafのdepthの最大値。単一nodeのtreeのheightは0。
巡回方法は3つ:
- Preorder Tree Walk: root, left, right
- Inorder Tree Walk: left, root, right
- Postorder Tree Walk: left, right, root

Binary Search Tree

ALDS1_8_A, ALDS1_8_B, ALDS1_8_C: 二分探索木。全てのnodeに関して、「左の子 <= node <= 右の子」が成立するBinary TreeをBinary Search Treeという。

Inorder Tree Walkをすると昇順に並べられたキーを得ることができる
Time Compexity:
- insert, lookup, delete: 平均 $O(log_2N)$, 最悪 $O(N)$
- 高さhに対して $O(h)$ となるため。なので、高さが低くなるよう工夫する必要がある。

Balanced Binary Search Tree

平衡二分探索木。高さが可能な限り低く保たれている木をBalanced Treeと言い、BalancedなBinary Search Treeは上記の計算量の問題を改善できる。

Time Complexity:
- insert, lookup, delete: 最悪か償却解析(Amortized Analysis)で $O(log_2N)$

Self-balancing Binary Search Treeには以下のような実装がある:

1) AVL Tree

最初に考案されたSelf-balancing Binary Search Tree。回転と呼ばれる操作を行なうことにより、全てのnodeの左右部分木の高さの差も1以下になるという条件を満たし続ける。

次に述べるRed-Black Treeに比べ平衡性をより厳密に維持するためlookupはAVL木の方が速いが、insertやdeleteで毎回平衡条件の判定を行なうためそれらが頻繁に行なわれるとRed-Black Treeより性能が出なくなる。

2) Red-Black Tree

以下の条件を満たすBinary TreeをRed-Black Treeという。

nodeは赤か黒に分類される
rootは黒である
赤いnodeの子は黒である
全てのleafからrootへのパス上に同じ個数の黒いnodeがある

最後の性質により、rootからの最も長いパスは赤と黒が交互に現われ、最も短いパスは黒だけになるので、rootからのパスの長さの差が最大でも2倍以内に収まっていることになる。
この状態を維持するためには、このような操作が必要になる。

3) Treap

各nodeに乱数を割り振りそれに基づいてBinary Heapを作る。Binary Heapで本来無規定である左右の関係に関しては、乱数ではなく探索対象の値の方でBinary Search Treeのルールで並べる。insert時はBinary Search Treeとして適切な場所に挿入した後、木の回転を使って乱数に関してBinary Heapを成立させることで平衡性を維持する。

TreeとHeapを融合しているためTreap。

Complete Binary Tree

ALDS1_9_A: 完全二分木。leafのdepthの差が最大1以下で、最下位レベルのleafが左から埋まっているもの。最下位でないレベルは全て埋まっている。必ずBalanced Binary Treeになる。

height (node数が$N$のとき): $floor(log_2 N)$
- $0$: $N=1$
- $1$: $N=2…3$
- $2$: $N=4…7$

$2^1$	$2^2$	$2^3$	$2^4$	$2^5$	$2^6$	$2^7$	$2^8$	$2^9$	$2^{10}$
2	4	8	16	32	64	128	256	512	1024

以下のデータ構造と関連している:

1) Binary Heap

ALDS1_9_B: Complete Binary Treeの各nodeのキーが1つの配列の各要素に対応するように表されたデータ構造。論理的にはComplete Binary Treeなものの、実装は1オリジンの1次元配列になる。単にHeapとも呼ぶが、Heap Memoryとは無関係。

Max Heap: 各nodeのキーが親のキー以下になる
Min Heap: 各nodeのキーが親のキー以上である
あるnodeのインデックス(1オリジン)をiとすると、親はi/2、左の子は2*i、右の子は2*i+1になる。
- 親子にのみ大小関係があり兄弟間に制約はないため、rootから値を取り出すのに向いている。

2) Priority Queue

ALDS1_9_C: キーを挿入した後、最大のキーから順に取り出せるデータ構造。上記のBinary Heapを使うと効率的に実装できる。

Time Complexity:
- insert: $O(log_2 N)$
  - 配列の末尾に値を追加した後、親を辿ってより大きな値があれば交換し続けるとMax Heapが維持できる。そのため最大で木の高さ分の操作が必要。
- extract max: $O(log_2 N)$
  - rootを取り出した後、配列の末尾をrootに持ってきた後、左右の子のうち大きい方と交換するのを子に向かって再帰的に繰り返すとMax Heapが維持できる。最大で木の高さ分の操作が必要になる。

3) Binary Indexed Tree

Fenwick treeともいう。各nodeが持つ値を部分木の要素の和としたツリー構造。数列と任意のiが与えられた時に、$a_1 + a_2 + ... a_i$を高速に計算できる。通常はBinary Heapのように1つの配列上で親子関係を表現して実装するため、

Time Complexity: 更新および部分和の計算が $O(log_2 N)$

4) Segment Tree

各nodeがあるrangeに対応づいたComplete Binary Tree。各nodeに何を持つかは自由なので様々なrangeに対して応用が効き、Complete Binary Treeであるので計算量は$O(log_2 N)$になることが期待できる。

参考: セグメント木とは

B-tree

多分岐のBalanced Tree。各nodeからN個の枝が生えている時order NのB-treeといい、各nodeはN-1個のキーを持つ。枝1から枝N、キー1からキーN-1を持つ時、枝iはキーi-1より大きくキーiより小さいキーだけを保持する。

ブロック型記憶装置でのデータ検索に向いており、各node(ページ)のサイズが外部記憶装置のブロックサイズの整数倍になるようにorderを調整すると、Binary Search Treeに比較して非常に効率が良くなる。逆にBinary Search Treeはブロック型でない記憶装置に向いている。

B+ tree

基本的にはB-treeと同じだが、B-treeと違ってレコードはleafにのみ存在し、internal nodeにはキーのみが格納される点が異なる。leafには次のleafへのポインタが格納されており、レコードの高速な線形探索が可能になっている。

ReiserFS、XFS、JFS2、HammerFS、NTFSといったファイルシステムや、MySQLのInnoDBがB+ treeを利用している。

PostgreSQLはGiSTでB+ treeを使うこともできるが、通常のインデックスにはB+ treeではなくB-treeが使われている。これはInnoDBはインデックスにレコードを保存するのに対して、Postgresはテーブルのデータを常にtable heapに保存するため、B+ treeかどうかの議論があまり関係がないことによる。

Trie

Prefix Tree, Radix Tree, Digital Treeとも言う。あるキー文字列に対応する値を取り出すことができるデータ構造。各nodeは自身に対応するprefixがあり、rootを空文字列とし、leafおよび一部のinternal nodeがキーに対応した値を格納する。

Hash Tableの代替にでき、理論上平均検索性能は同じだが、実測するとTrieの方が速く、キーの衝突が発生しないといった利点がある。一方、Hash Tableに比べメモリ効率が悪く、全キーを文字列として取り出すのが困難であるといった欠点がある。

Time Complexity: キー文字列の長さが一定の時$O(1)$とみなせる
- キーがN個ある時、文字の種類がkなら、最も長いキーの長さの下限は$log_kN$文字なので、探索時間は厳密には: $Ω(log_kN)$

Set

Disjoint-set Forest

DSL_1_A: Union-Find forestとも言う。データの集合を互いに素である集合に分割して管理するデータ構造。

主に以下の2つの操作(Union-Find Algorithmと呼ぶ)をサポートするデータ構造をDisjoint-set data structureという。

Find: ある要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使える。
Union: 2つの集合を1つに統合する。

これの実装にはいくつかパターンがあるが、Linked Listを使ったものは遅く、木構造を使って素集合を管理するようにしたDisjoint-set Forestと呼ばれるデータ構造を使うとより高速に実現できる。

計算量を$O(log N)$に抑えるためには木構造の平衡を保たないといけない。Disjoint-set Forestでは、以下の2種類の方法でこの問題を改善する:

Union by rank: union時、2つの木の大きさ(rank)を評価して大きい方の木を全体のrootにする
Path compression: find時、findしたnodeをrootに繋ぎ変える

これらの手法は相補的なため、両方適用することで最も高速になる。

3. その他

Big O notation

Backman-Landau NotationやAsymptotic Notationともいう。

O, o: 漸近的なupper boundを記述するために使われる
Ω, ω: 漸近的なlower boundを記述するために使われる
Θ: upper boundとlower bound両方に抑えられる時に使われる

P vs NP

計算複雑性理論において、YesかNoで答えられるような判定問題には、以下のような複雑性クラスの分類がある。

P: 決定性チューリングマシンによって多項式時間(Polynomial time)で解かれるものの全体。Pが以下のNPに含まれることは自明。
NP: 非決定性チューリングマシンによって多項式時間で解くことができる問題。Non-deterministic Polynomial time.
- これは「Yesとなる証拠が与えられた時、その証拠が正しいか多項式時間で判定できる問題」と同値になる。
- 例えば与えられたグラフにハミルトン閉路(全ての頂点を一度だけ通る閉路)が存在するかどうか判定する多項式時間で解けるアルゴリズムは知られていないが、答えが与えられれば検算可能なため、NPに属する。
NP-hard: NPに属する任意の問題から帰着可能な問題の集合。
- NPと比べて少なくとも同等以上に難しいが、NPに属するとは限らない。例えば停止問題はNPである充足可能性問題から用意に帰着可能なためNP-hardだが、停止問題は一般に決定不可能なためNPではない。
NP-complete: NPに属し、かつNPから多項式時間還元(帰着)が可能(NP-hard)なもの。
- Knapsack問題の特殊ケースである部分和問題はNPかつNP-hardである。
- 巡回セールスマン問題の特殊ケースであるハミルトン閉路問題はNPかつNP-hardである。

参考文献

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up