アルゴリズム

サブカテゴリ

• ソート

チェックポイント

• 幅優先探索 Basis 幅優先探索（BFS）は選ばれた始点から距離 k の頂点をすべて訪問してから距離 k+1 の頂点を訪問するという形でグラフを層ごとに探索する。このチェックポイントではキューを使った BFS の導出、重み無しグラフで最短距離を計算することの証明、$O(V+E)$ の実行時間の分析を行う。
• 二分探索 Basis 二分探索（binary search）はソート済み配列から $O(\\log n)$ 時間で値を見つける。各ステップで探索区間を半分にすることで達成する。このチェックポイントでは、アルゴリズムの導出、不変条件の解説、そして境界の更新を誤ると正しさが破壊される仕組みを示す。
• 深さ優先探索 Basis 深さ優先探索（DFS）は各頂点からバックトラックする前にできる限り深く探索する。このチェックポイントでは再帰版と明示的スタック版の両方を導出し、閉路検出やトポロジカルソートなどの応用を可能にする発見時刻と完了時刻をトレースし、$O(V+E)$ の実行時間を分析する。
• アルゴリズム入門 Basis アルゴリズムとは入力を出力に変換する有限で明確な手続きだ。このチェックポイントでは、ある手続きがアルゴリズムたる条件を説明し、正しさと効率という常に問うべき 2 つの問いを示し、以降のアルゴリズムファミリーを概観する。
• 漸近的記法 Basis ビッグ O、ビッグ Ω、ビッグ Θ は関数が入力の増大に対してどう増えるかを語るための言語だ。このチェックポイントでは各記法を厳密に定義し、上界・下界・タイト境界を対比し、ハードウェアや定数を気にせずアルゴリズムを比較できる仕組みを示す。
• 時間計算量 Basis 時間計算量（time complexity）は入力サイズに対してアルゴリズムの実行時間がどう拡張するかを数える。このチェックポイントでは基本操作の数え方、漸近的記法による表現、そして一般的な制御フローパターンから支配的なコストを読み取る方法を解説する。