アルゴンクイズ – アルゴリズムの奥深さを探る
アルゴリズムは、コンピューティングの基盤を成すものです。様々なデータ構造とアルゴリズムの組み合わせによって、私たちが利用するシステムが支えられています。本クイズでは、ソート、グラフ探索、Union-Find、ハッシュテーブル、文字列検索など、アルゴリズムの奥深さに迫ります。アルゴリズムの特性と計算量の理解を深めながら、コンピューティングの根幹に迫る知的挑戦に挑んでみましょう。
Q1 : 単一始点最短経路を求めるアルゴリズム Bellman–Ford が追加で検出できるものは次のうちどれか？ 負の重みを含むサイクル（負のサイクル）の存在 全ての負辺を正に変換する変換方法 最短路の個数が無限であること 任意の重み付きグラフが非負重みであること
Bellman–Ford 法は反復的に緩和操作を行い、最大で頂点数-1 回の反復で最短距離を求めます。さらに追加の反復を行うことで、距離がさらに更新される（さらに短くなる）経路があれば負の重みサイクルが存在すると判定できます。したがって負のサイクルの検出が可能であり、これは Dijkstra 法では直接行えない特性です。
Q2 : KMP（Knuth–Morris–Pratt）文字列検索アルゴリズムにおけるパターンの部分一致テーブル（失敗関数）の前処理の時間計算量はパターン長 m を用いてどれか？ O(n)（テキスト長に依存） O(m) O(nm) O(m log m)
KMP アルゴリズムではパターン（長さ m）に対して接頭辞・接尾辞の一致を利用する失敗関数（lps や prefix 関数）を前処理で構築します。この前処理はパターン長 m のみを参照し、線形時間で計算できるため O(m) です。本体の検索はテキスト長 n の処理を加えて O(n + m) となります。
Q3 : クイックソートが最悪計算量 O(n^2) を引き起こす典型的なピボットの選び方はどれか？ ランダムにピボットを選ぶ 中央値近似（例: median-of-three）を使う 常に配列の中央の要素を選ぶ 既に整列済みの入力に対して常に先頭要素をピボットに選ぶ
クイックソートはピボットによって分割が偏ると深さが増し最悪 O(n^2) になります。特に既に昇順や降順に整列された入力に対して常に先頭要素をピボットに選ぶ戦略は、各分割で一方にほぼ全要素が偏り、再帰が深くなって最悪ケースを引き起こします。ランダム選択や median-of-three はこの偏りを緩和します。
Q4 : 二分ヒープ（二分ヒープ配列表現）における build-heap（配列からヒープを構築する操作）の計算量はどれか？ O(n) O(n log n) O(log n) O(n^2)
配列からヒープを構築する際の一般的なアルゴリズム（下から非葉ノードに対して heapify を行う方法）は各レベルでの操作回数とノード数の関係により総コストが O(n) になります。個々の heapify は最悪 O(log n) ですが、多くのノードは浅い位置にあり合計で線形時間に抑えられます。要素を1つずつ insert する方式だと O(n log n) になる点と対照的です。
Q5 : ダイクストラ法（Dijkstra）が単一始点最短経路問題に対して正しく適用できるための必要十分の条件はどれか？ グラフが有向であること 全ての辺の重みが非負であること 始点から到達できる頂点数が有限であること グラフが連結であること
ダイクストラ法は頂点の最短距離が確定した順に確定させる貪欲法で、エッジの重みが非負であることが計算の正当性の鍵です。負の辺があると、すでに確定した距離が後で小さくなる可能性があり誤った結果になります。グラフの有向・無向や連結性は状況により扱えますが、正しさの前提は「辺の重みが非負であること」です。
Q6 : ハッシュテーブル（適切なハッシュ関数と負荷率を保つ場合）の平均的・期待される探索（検索）時間のオーダーはどれか？ O(n) O(log n) O(1) O(n log n)
ハッシュテーブルは衝突解決（チェイニングや開番地法）を適切に行い、負荷率を一定に保てば、キーの探索（挿入・削除・検索）の期待時間は定数時間、すなわち O(1) になります。これは平均的・確率的な議論に基づくもので、最悪ケース（悪いハッシュ関数や全衝突など）では O(n) になることがありますが、実用的には期待 O(1) が利点です。
Q7 : トポロジカルソート（拓扑ソート）が定義され、実行可能なのはどのようなグラフか？ 無向グラフ全般 有向グラフにサイクルが存在するグラフ 重み付きグラフのみ 有向非巡回グラフ（DAG: Directed Acyclic Graph）
トポロジカルソートは有向グラフの頂点を「有向辺の向きに従って前後関係が保たれる順序」で並べる操作であり、これが可能なのはグラフに有向サイクルが存在しない場合、つまり DAG の場合のみです。有向サイクルがあると順序矛盾が発生してトポロジカル順序は存在しません。無向グラフや重みの有無は本質的な条件ではありません。
Q8 : 以下のソートアルゴリズムのうち、安定でありかつ平均・最悪ともに O(n log n) の時間計算量を持つものはどれか？ マージソート クイックソート ヒープソート 選択ソート
マージソートは分割統治法に基づき配列を分割して再帰的にソートし、マージ操作で安定性を保ちながら要素を結合します。計算量は分割とマージの各段階で O(n) を要し、深さが O(log n) のため平均・最悪ともに O(n log n) です。一方クイックソートは平均 O(n log n) だが最悪 O(n^2)、ヒープソートは O(n log n) だが安定ではなく、選択ソートは O(n^2) です。
Q9 : 負の重みの辺を含むグラフでも単一始点最短経路を正しく計算できるアルゴリズムはどれか？ ダイクストラ法 ベルマン–フォード法 幅優先探索（BFS） A*（エースター）
ベルマン–フォード法は負の重みを持つ辺が存在する場合でも単一始点最短経路を計算でき、負のサイクルが存在するかどうかも検出できます。ダイクストラ法は負の辺があると誤った結果を出す可能性があり、BFSは重みが等しい（無重み）グラフ用、A*はヒューリスティックに依存する探索であり一般に負辺を扱う保証はありません。
Q10 : Union-Find（Disjoint Set Union）において、経路圧縮とランク（またはサイズ）別統合の両方を用いたときのアモルタイズ（平均）操作コストのオーダーはどれか？ O(log n) O(1) 逆アッカーマン関数にほぼ等しい O(α(n)) O(n)
経路圧縮とランク別統合を組み合わせた Union-Find の各操作（Find, Union）のアモルタイズ時間は逆アッカーマン関数α(n)にほぼ等しい定数に非常に近い増加率を示します。理論的には O(α(n)) であり、α(n) は実用的な n の範囲ではほぼ定数（例えば ≤ 4 や 5）なので高速です。O(1) と表現されることもあるが厳密には α(n) を用いて表されます。
まとめ
いかがでしたか？ 今回はアルゴンクイズをお送りしました。
今回はアルゴンクイズを出題しました。
ぜひ、ほかのクイズにも挑戦してみてください！
