1.4アルゴリズムと計算量

前節でデータ構造ごとの計算量特性を学んだので、この節ではその上で動くアルゴリズムそのものの効率を評価します。応用情報技術者試験では、擬似言語で書かれたアルゴリズムを読んで計算量を判定させる問題は出ませんが（午後の範囲）、オーダ記法で効率を比較し、状況に応じて適切な手法を選ぶ判断力は午前でも重要な出題テーマです。

1.4.1オーダ記法

• オーダ記法（O記法）＝入力サイズnが増加したときの処理時間（またはメモリ量）の増加傾向を表す記法。定数倍や低次の項を無視し、支配的な項だけで表す（例：3n^2+5n+2 は O(n^2)）。
• 代表的なオーダを小さい順に並べると O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)。入力サイズが大きくなるほど、この差は劇的になる——例えばn=1,000,000のときO(n)は100万回だがO(n^2)は1兆回の演算が必要になる。

1.4.2探索アルゴリズム

• 線形探索＝先頭から順に1件ずつ比較する探索。整列不要だがO(n)。2分探索＝整列済みデータに対し、中央の値と比較して探索範囲を半分に絞り込むことを繰り返す探索でO(log n)——ただし事前にデータが整列済みである必要がある。
• ハッシュ探索は前節の通り平均O(1)だが、要素数が少ない・メモリ制約が厳しい場合は2分探索や線形探索の方が実用的な場合もある。

1.4.3整列アルゴリズムと安定性

• クイックソート＝基準値（ピボット）より小さい要素と大きい要素に分割することを再帰的に繰り返す整列法。平均O(n log n)だが、ピボットの選び方が悪い（既に整列済みのデータで常に先頭を選ぶ等）と最悪O(n^2)まで悪化する。
• マージソート＝データを半分に分割し、それぞれを整列してから統合する（併合する）整列法。常にO(n log n)を保証するが、統合のために元データと同サイズの追加メモリを要する。
• ヒープソート＝前節のヒープ構造を使い、最大（または最小）要素の取得・削除を繰り返して整列する方法。常にO(n log n)を保証し、追加メモリもほぼ不要（in-place）という長所を持つ。
• 安定性＝整列の前後で、キーの値が等しい要素どうしの相対順序が保たれるかという性質。マージソートは安定、クイックソート・ヒープソートは（実装によるが標準的な方式では）不安定。「氏名でソート済みのデータを部署でソートし直しても氏名順が保たれてほしい」といった多段ソートで安定性が重要になる。

あるバッチ処理で100万件の売上レコードを整列する場面を考えます。まずクイックソートを採用したところ、既に日付順にほぼ整列済みのデータに対してピボットを常に先頭要素から選ぶ実装だったため、分割が偏り続けて最悪ケースのO(n^2)に近い挙動となり、処理が異常に遅くなりました。対策として、ピボットをランダムまたは中央値近似で選ぶよう改善するか、常にO(n log n)を保証するマージソートやヒープソートへ切り替えるという判断になります。ここでメモリ制約が厳しい組み込み系のバッチであれば、追加メモリがほぼ不要なヒープソートを、逆にメモリに余裕があり「氏名でソート済みのデータを部署コードで再ソートしても、同じ部署内では氏名順を保ちたい」という多段ソート要件があるなら、安定性を持つマージソートを選ぶのが妥当です。次に検索の場面を考えると、この100万件のデータから特定の売上IDを検索する処理を毎回線形探索（O(n)）で行っていたとします。データが整列済みであれば2分探索に切り替えるだけで log2(1,000,000) ≒ 20 回程度の比較で済み、劇的な高速化が見込めます。このように、同じ「整列」「検索」という目的でも、データの性質（整列済みか、メモリ制約はあるか、安定性が必要か）によって最適なアルゴリズムは変わるという判断軸が、レベル3で問われる実務的思考力です。

1.4.4再帰・分割統治・動的計画法・グラフ探索

• 再帰＝自分自身を呼び出して問題を解く手法。分割統治法は問題を小さな部分問題に分割し、それぞれを再帰的に解いてから結果を統合する設計方針（マージソートやクイックソートはその代表例）。
• 動的計画法（DP）＝部分問題の計算結果をメモ化（記録して再利用）することで、同じ部分問題を何度も計算する無駄を省く手法。フィボナッチ数列の単純な再帰はO(2^n)だが、DPでメモ化すればO(n)まで削減できる。
• 幅優先探索（BFS）＝キューを使い、始点から近いノードを優先して探索する方法で最短経路（辺の重みが均一な場合）を求めるのに適する。深さ優先探索（DFS）＝スタック（または再帰）を使い、行けるところまで一気に進んでから戻る探索で、全経路の列挙や閉路検出に適する。

1.4.5この節のまとめ

• オーダ記法は支配的な項だけで表す。O(1)<O(log n)<O(n)<O(n log n)<O(n^2)の順で効率が下がる
• クイックソート（平均O(n log n)・最悪O(n^2)・不安定）とマージソート/ヒープソート（常にO(n log n)）を使い分ける
• 動的計画法は部分問題をメモ化して重複計算を排除、BFSは最短経路、DFSは全経路探索・閉路検出に向く