> For the complete documentation index, see [llms.txt](https://hayashier.gitbook.io/article/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hayashier.gitbook.io/article/software/algorithm-overview.md). # アルゴリズムとデータ構造 入門 ## アルゴリズムとデータ構造 入門 アルゴリズムとデータ構造について、基本的な内容の復習がてらまとめました。 ### データ構造 動的なデータの集合を効率的に扱う役割 #### 1つの集合を主に扱う * 配列 * リスト * 連結リスト * 双方向リスト * 番兵と呼ばれる特別なノードを1つ持ち、これをsentinelとする。sentinelは実際に扱うデータには含めないが、これを起点にノードがつながっていく * スタック * キュー * 巡回待ち行列、リングバッファー * データの格納領域が末尾に偏り先頭が空の状態になり記憶領域の効率的な活用 * 木構造 * 二分木 * 各節点から出る枝は2本以下 * 完全二分木 * 狭義の二分木 * 根から葉までの高さの差が全ての葉で0のとき * 広義の完全二分木 * レベルiでは節点の数は2^i個のように最大に配置し、最も深い深さであるレベルhでは左詰め * 二分探索木 * 根より左部分木にあるすべてのデータはその節点のデータよりも小さい。節点より右部分木にあるすべてのデータはその節点のデータよりも大きい * 探索効率 * 最適二分探索木 : 左部分木と右部分木が根を中心に左右バランスが良いとき n/2^h=1 よりO(logn) * 最悪二分探索木 : 左部分木のみで右部分木が空のときO(n) * データの削除 * 削除すべき節点に右部分木がなく左部分木がある場合、左部分木を削除した節に据える * 削除すべき節点に左部分木がなく右部分木がある場合、右部分木を削除した節に据える * 削除すべき節点に2つの子がある場合、左部分木の中で最大のデータの節点、もしくは右部分木の中で最小のデータの節点を、削除する節点へ移す * 完全二分木にならないと探索効率がO(n)に落ちる * 平衡木 * 完全二分木に近い最適二分木にするためになるべく左右バランスが取れた平衡器を作る * 以下、大きく2通りの方法　 1. 格納されたアンバランスな二分木の構造を完全二分木構造に近づけるようにデータを再配置する 2. 二分木構造にこだわらず、データを葉にのみ各区脳することによって根から浜での木の高さをつねに一定に保つようなデータ構造。さらに2通りの方法 1. 既に格納されたアンバランスな二分木からデータを取り出してもう一度バランスのとれた二分探索木に作り直す 2. データを格納するたびに1重回転、2重回転という方法を使ってデータ配置の対称性を保つ方法 * AVL木という平衡木を作る * 木の高さを常に一定にするためにデータ構造にB木という多分木を使用する。このデータ構造は最もバランスがとれた完全二分木 * AVL木 * 最悪計算量がO(logn) (厳密には木の高さhはO(logn)なので、O(1.4441log(n+1))) * どの節点をとっても左部分木と右部分木の高さの差が1以内にする二分木 * アデルソン-ヴェルスキーとランディスというロシアの数学者の頭文字から名付けられた * 二分探索木床となる点はバランスファクタという変数bfが用いられ左右部分木の高さを常に監視し、バランスファクタが2以上になれば、並行が崩れたと判断して単一回転や二重回転操作により平衝を回復 * 各節点にバランスファクタを持たせる * bf=(右部分木の高さ)-(左部分木の高さ) * 回転方法 * 左部分木が高い場合(bf=-2) * 左部分木の高さが増加し、ある節点でbf=-2になれば、これを親とするこの接点でさらに左部分木が高い(bf=-1)の場合は、単一LL回転 * そうではない場合は、すなわちbf=-2になっている親の子の右部分木が高いことになるので、2重LR回転 * 右部分木が高い場合(bf=2)の場合についても同様 * 右部分木の高さが増加し、ある節点でbf=2になれば、これを親とするこの節点でさらに右部分木が高い(bf=1)の場合は、単一RR回転 * そうではない場合は、すなわちbf=2になっている親の子の左部分木が高いことになるので、2重RL回転 * LL回転のLLは左部分木の節点とその左の葉という意味 * 経験則 * 経験的に回転操作は平均的にほぼ2回の挿入に1回必要 * 1個のキーの挿入が高々1回の回転しか生じない * 削除では探索経路のすべての節点で回転が必要な場合が生じるが特殊な場合で、経験的に削除の場合5回に1回しか回転操作が必要とされない * 挿入や削除の頻繁に起こるデータベースでは再平衡化のため効率が低下するおそれがある * B木 * 根から葉までの木の高さを常に一定に保つ多分木探索木 * 常に平衝木として保たれているので、二分探索木より高速な探索ができる * 仮想構成ファイルやデータベースに広く利用される * k次のB木は根以外の節点にはk≦m≦2kを満たすm子のキーを含む * 全ての葉は同じレベルにある * 挿入 * 既に格納されているキーの数が2k個ある場合 1. これ以上節点にキーを挿入できない場合は、挿入したいきーと格納済みの節点のキーを照準に並べる 2. キーの数2k+1個を2で割った商を四捨五入し、照準されたキーからその商の値に相当する順位のキーの値を親節点に挿入 3. 解消されるまで上記手順を繰り返す * 削除 * 削除したときに節点のキーの個数がk個未満の場合 * 節点が根のときは、削除するキーよりも大きい次の葉を新しい根として古い根を削除 * 節点が根ではなく、右端の節点ではない場合、親と右の節点からキーを移す * 節点が根ではなく、右端の節点ならば親と左の節点からキーを持ってくる * 右の節点のキーもk個未満になる場合は、節点の親のキー1つを移し、右節点のキーと併合し、空になった右節点は削除 * 解消されるまで上記手順を繰り返す * 発展 * B+木 * データが葉だけに格納されているので、データは同一レベルにあり順アクセス可能な整列された列になっている * 直接アクセスと順アクセスとに適した構造を兼ね備えている * 動的環境にも向いているので仮想編成のデータ構造として用いられる * 2-3木 * 葉以外の内部節には2個あるいは3個の個を持ち、葉がすべて同一レベルにあるような多分木探索木 * B+木、2-3木の最悪計算量はO(logn) * 赤黒木(Red-Brack Tree、2色木) * 基本的な動的集合操作に対して最悪実行時間O(logn)を保証する平衝二分探索木 * 以下5つの2色条件をすべて満たす二分探索木 1. 各節点は赤または黒のどちらかである 2. 根は黒である 3. すべての葉(NIL)は黒である 4. ある節点が赤ならばその子は共に黒である 5. 各節点について、その子孫の任意の葉を結ぶパスは同数の黒節点を含む * 条件を満たすように赤黒をつけかえるかローテーションしながら平衝を保つようにする * 最短パスは黒節点のみ。最長パスは赤黒が交互に含まれる * パスの節点の配色を制約することで、ある道の長さが他のある道の長さの2倍を超えることがないことを保証し、木をおおよそ平衝にしている * JavaのTreeMapの実装にも使用される * アルゴリズム * 検索 : 二分探索木の検索 * 挿入 : 詳細は、[赤黒木 Red-Black tree](http://fujimura2.fiw-web.net/java/mutter/tree/red-black-tree.html)を参照 * 削除 : 同上 * ヒープ * (積み重ねた)山という意味 * どの親と子の節点をとってもそれらの接点間で(親節点のデータ)≦(子節点のデータ)もしくは逆の関係をみたす二分木 * 二分探索木よりもゆるい規則の順序木 * 半順序木とも言われ配列で表現されることもある。親kとすると左の子は2k、右の子は2k+1 * 挿入 * 末尾にデータを追加し、関係が崩れたら親のデータと子のデータを入れ替えていく * 削除 * 先頭のデータを取り出し、末尾のデータで置き換え、関係が崩れたら親のデータと子のデータを入れ替えていく * 計算量はO(n\*logn) * ヒープソートにも活用 * 処理 * アップヒープ * ダウンヒープ * ビルドヒープ * 活用例 * 優先度付きキュー #### 複数の集合の管理 森の構造を応用した、互いに素な集合の管理を行うデータ構造 * Union-Find木 * 各ノードが、その親ノードの番号を保持する森によって、互いに素な集合を表すことができる。ランクによる木の合併と経路圧縮によって、質問へ高速に答えることができるデータ構造 * 森の各木が1つの集合を表す。各集合の代表をその木の根とする。各ノードが属する集合の番号を、その集合の代表の番号とする * 操作 * findSet(x)はノードxの代表を求める操作だが、同時にxからそれが属する木の根までの経路を圧縮 * 2つのノードx,yが属するそれぞれの集合を合併するときは、それぞれfindSet(x),findSet(y)によって代表を求め、これらのランクに基づいて合併 * 2つの要素xとyが同じ集合に属するかの質問に対してはそれぞれのfindSetの値が等しいか調べる * 合併の処理、質問の処理、両方において経路圧縮が行われるため、それぞれの処理・質問において、高さが極めて低い木に対して操作が行われる * グラフの最小全域木を求めるクラスカルのアルゴリズムに応用 * 互いに素な集合に対する、合併処理と質問に答える問題は、グラフの探索アルゴリズムなどでも解決することができるが、グラフの場合はエッジの接続性が変更されたあとに探索をすることになり、大きなデータに対しては応用できない * 互いに素な集合の管理(Disjoint Set) * 1つの要素が複数の集合に属さないような集合 * ランクによる合併 * 木の高さ(ランク)を考慮して、2つの木を合併 * 2つの木の高さが異なる場合は、高さが低い方の木の根の親を、高さが高い木の根として書き換え木を合併 * O(1) * 互いに素な集合の基本操作に応用 * 経路圧縮 * 深さ優先探索のバックトラックの原理で、始点ノードから根までの経路上にある全てのノードの親を、根に更新していく * 訪問したノードから親ノードに向かって更新していく * O(N) * 工夫によって高さの低い木が生成され、木に対する走査が極少ない計算量で行われるようになる * 互いに素な集合の基本操作に応用 * グラフ * 全域木 : 連結なグラフからエッジを選択(削除)して得られる連結な木 * 最小全域木 * プリムのアルゴリズム * 適当なノードを起点として全域木Tを拡張していく。各ステップで、Tに含まれるノードとTに含まれないノードを繋ぐエッジの中で重みが最も小さいものを選び、その端点であるTに含まれないノードをTに含めていく　 * 重みが最小のノードを探す処理を線形探索で行う場合はO(N^2) * 最小の重みをヒープ(優先度付きキュー)で管理し、グラフを隣接リストで実装した場合はO((N+M)logN) * クラスカルのアルゴリズム * グラフのエッジをそれらの重みの昇順で整列。重みが小さい順にエッジ(u,v)を選び、uとvが異なる集合にある場合にこれらの集合を合併し、(u,v)を最小全域木に追加。同じ集合に属する場合はエッジを追加するとグラフに閉路がでｋるので、そのエッジを捨てる。 * 追加したエッジの数がN-1に達したときに終了 * 計算量はエッジに対するソートアルゴリズムに依存。クイックソートはマージソートを使えばO(MlogM) * 大規模なグラフに対しても利用可能 * 最短経路 * ダイクストラのアルゴリズム * 各計算ステップでは、始点からTに含まれないノードから暫定距離distが最も小さいノードuを選び最小経路木Tに含めていく。選ばれたノードに隣接するノードの暫定距離を更新し、暫定距離が最小のノードを探していく操作を繰り返していく。 * 最短経路木におけるノードvの親parent\[v]をuに更新 * 始点から他の各ノードまでの最短経路はparentを用いて構築できる * 暫定距離が最小のノードを探す処理を線形探索で行う場合はO(N^2) * ヒープ(優先度付きキュー)を用いることでO((N+M)logN) * 要素の取り出しにO(NlogN)、暫定距離を更新してヒープに要素を追加するためにO(MlogN) * 負の重みのエッジを持つグラフに対しては正しく動作しない * ベルマンフォードのアルゴリズム * 始点からの各ノードiまでの暫定最短距離を更新していく * ダイクストラのアルゴリズムでは選択された最適なノードに隣接するノードの暫定距離を更新するが、このアルゴリズムでは全てのエッジを操作する処理を繰り返す * N回目の繰り返しでdistの更新が発生すると、負のサイクルが発生していることを検出 * グラフに含まれるM個のエッジを合計N回操作するのでO(NM) * 暫定距離の更新が止まったら処理が打ち切られる * そのため、グラフの形状とエッジの重みの特性によっては高速に動作 * 負の重みのエッジがあるグラフを扱うアプリケーションに活用できる * ダイクストラのアルゴリズムより計算効率は劣る * ワーシャルフロイドのアルゴリズム * 重み付き有向グラフの隣接行列を全てのノードの組(i,j)間の最短距離を表す行列に変換 * iからjへの経路でkが含まれないときはdist\[i]\[j]の値は維持。含まれるときはdist\[i]\[k]+dist\[k]\[j]の値のほうが小さくなり更新 * 負の重みを持つグラフに対しても適用することができ、アルゴリズム終了時点であるノードがそれ自身のノードへの最短距離が負になっていれば、負の閉路を検知可能 * N個の経由点に対して、全てのノードの組(N\*N)だけ距離の更新が行われる可能性があるのでO(N^3) * すべての始点・終点の組に対する最短距離を求める問題、負の重みを持つグラフに対する問題、ノード間の到達性を調べるアプリケーションなどに応用可能 ### ソートアルゴリズム * バブルソート(単純交換ソート) * 隣接する2つのデータを比較し、データの大小関係が逆のとき、2つのデータを入れ替えを行って整列を行い、大小関係の逆のデータがなくなるまでこれを繰り返す * 配列を前方のソート済み部分と後方の未ソート部分に分け、隣り合う要素を比較し逆順の組をスワップする処理を繰り返し、ソート済みの要素を決定していく * 計算量はO(n^2) * 交換回数=(n-1)+(n-2)+....+2+1=N(N-1)/2 * 安定。すなわち、ソートのあとでそれらの要素の順序が保たれる * シェーカーソート * バブルソートの無駄な皮革部分を行わず、また比較方向を両方向にすることにより、ソート効率を上げる * バブルソートでの問題点 * バブルソートでは、整列途中、データが正しく並んでいる場合でも、データのおしまいまで比較を無条件に繰り返すため、非効率 * データ交換を行った場合、交換した配列の引数値を変数に格納しておき、次回の比較では整列済みの配列を比較しないように整列済みの位置を記憶させておき、この位置を入れ替え限界として次回の整列時に利用 * 前方から後方へと一方向にのみ比較を行うので、データを照準にソートする場合、配列内の値が小さなデータは前方に集まるので遅くなる * 手順 1. 先頭から右に向かってバブルソートのように前後の要素の大小関係を比較していき、大小関係が逆のデータの入れ替えを行う。このとき、最後に配列が行われたインデックスも記憶しておく 2. 記憶していた要素のインデックスから先頭に向かってバブルソート。インデックス0が最小値になる 3. インデックス1から先程記憶していた要素のインデックスまでバブルソートを行う。記憶していたインデックスにその間の要素の最大値が入る 4. 整列範囲の右端から左端に向かってバブルソートのように、交互に方向を変更して入れ替えを実行していく * 単純選択ソート * 未ソート部から最小のキーを持つ要素を選択肢、未ソート部の先頭要素と交換することを配列の先頭から繰り返していく * 配列を前方のソート済み部分と後方の未ソート部分に分け、未ソート部分から最小値を探索し、未ソートの部分の先頭とスワップすることで、ソート済み部分へ追加していく * 比較回数は(n^2-n)2のため、O(n^2) * 安定ではない * 単純挿入ソート * 挿入操作を前方から順番に行うことでデータを整列 * 先頭から一つ一つ、参照範囲のインデックスを広げていき、新しいデータの順番がくずれているとき、データを後方から比較し、正しい位置になるまでデータの相互交換を繰り返して挿入位置を決定することを繰り返す * 計算量はO(n^2) * i回目で比較・移動がi/2回起こると考える * 昇順でソートされていれば一回の操作がO(1)のためO(N) * 降順でソートされていると一回の操作でi個の要素を操作するのでO(N^2) * ソート済みのデータに対しては非常に高速なため、クイックソートと併用することもある * 内側のループで隣り合う配列要素同士を比較 * 安定 * シェルソート * 配列要素を一定の間隔離れた位置にある要素に分けてグループ分けして挿入ソートを繰り返すことで、配列の要素を並び替える * 一定間隔hだけ離れた要素を比較して単純挿入法を行い、hを狭め1になるまでこれを繰り返す * 計算量はhの選び方によるが、実験的に平均O(n^1.25)程度。1,3,7,15,...,2^k-1の場合、O(n^(3/2))。最悪O(N^2) * ほぼ整列されたデータにたいして　高速に動作 * 安定ではない * クイックソート * ある数xを枢軸(pivot)とし、pivotを中心に、xよりも大きな数と小さな数にブロック化し、分割されたブロックに同じ操作をブロック内のデータ個数が1になるまで再帰的に処理していくことで整列を行う * 例えば、真ん中のインデックスの要素を基準として、配列中の各要素を2つのブロックにわけていく * a\[i]≧xとなるまでiを0から大きくしていく。a\[j]≦xとなるまでjを1ずつ増やしていく。その後、a\[i]とa\[j]を交換し、iを1増やし、jを1減らす * 計算量 * 基準値の選び方に依存 * 最小の場合、グループを2等分にしていくので、n回の比較をlogn回行うのでO(n\*logn) * 分割が1:n-1の場合、最悪の場合となり、n+(n-1)+....+1となりO(n^2) * 基準値の選び方 * 区間の中央位置にある値 * 乱数を使って基準値の位置決定 * 整列する範囲の中からいくつかの値をサンプリングしそれらの中央値 * 再帰呼び出しを使用するため記憶領域が必要になり、最悪の場合O(n) * 計算手順は二分木構造におけるpre-orderの巡回に基づいている * in-place処理 * 最も高速に動く整列アルゴリズムの一つ * データの隔たりや安定性の問題に対する工夫は必要 * マージソート * データを2つのブロックに分け、前半と後半のブロックをそれぞれ整列し、整列したデータをマージする操作を再帰的に行うアルゴリズム * 大量のデータを整列する場合、主記憶装置に全データが入り切らず、補助記憶装置を利用して外部整列をする必要がある * マージソートでは、外部記憶装置に格納されているデータの一部を主記憶装置に読み込み、整列を行い、複数の整列済みデータをマージ処理により1つの整列済みデータを作成 * そのため、配列のデータ整列に使われることはあまりない * 計算量はO(n\*logn) * 二分木の葉以外のノードの数だけmergeが行われるが、各レベルでN回のデータの比較・移動が行われる。マージにおける二分木の高さはlog2 N * 安定 * 計算手順は二分木構造におけるpost-orderの巡回に基づいている * メモリーが必要になる欠点。外部ソート * 分割統治法 * 度数ソート(計数ソート) * 手順 1. 度数分布表の作成 2. 累積度数分布表の作成 3. 元の配列の各要素の値と累積度数分布表とをつきあわせて、ソート済みの配列を作る。対象の配列の値について累積度数分布表でのインデックスの値が、その値までに何人いるかを表す。そのため、累積分布表の値をインデックスとするところに目的の値を格納する。その際、累積度数分布表の値をデクレメントしておく。 4. 配列のコピー * データの最小値と最大値が予めわかっている場合にしか適用できない * 安定。ただし、手順3で元の配列の走査を末尾側からではなく先頭側から行うと、安定ではなくなる。 * ヒープソート * O(NlogN) * ダウンヒープをN回行う ### 探索アルゴリズム * 線形探索 * ランダムな整数列に対する探索 * 番兵法 * ループごとに i\