アルゴリズムで使う数学

プログラミング、特にアルゴリズムの学習を進めていると、「数学」の知識が必要になる場面にしばしば遭遇します。 「数学は苦手だったからプログラミングは難しいかも…」と不安に感じる方もいるかもしれませんが、ご安心ください。アルゴリズムでよく使われる数学の概念は限られており、高校や大学で学ぶような難解な数式を全て理解する必要はありません。

この記事では、アルゴリズムの理解と実装において特に重要となる数学的な考え方を、具体的なプログラミングの文脈と結びつけて紹介します。

1. 離散数学（論理演算と集合論）

コンピュータは突き詰めれば 0 と 1 の世界であり、離散的な（連続していない）値を扱います。そのため、離散数学の考え方はプログラミングの至る所に現れます。

論理演算（AND, OR, NOT, XOR）

もっとも身近なのが「論理演算」です。if 文などの条件分岐で日常的に使用しています。

• AND（論理積）: 両方の条件が真のときのみ真。
• OR（論理和）: 少なくとも一方の条件が真のときに真。
• NOT（否定）: 真偽を反転させる。
• XOR（排他的論理和）: どちらか一方のみが真のときに真。暗号化やビット演算などで頻繁に登場します。

集合論

データの集まりを扱う上で、集合の概念も重要です。

• 和集合・積集合・差集合: データベースのクエリ（SQL の JOIN など）や、配列同士のフィルタリングで、これらの考え方が使われます。
• プログラミング言語によっては Set というデータ構造がそのまま用意されており、重複を許さずにデータを管理する際に役立ちます。

2. 対数（Logarithm）

計算量の見積もり（オーダー記法）において、$O(\log n)$ という表記をよく見かけます。ここで登場する「対数（$\log$）」は、アルゴリズムの効率性を語る上で欠かせない概念です。

データの半減と対数

プログラミングにおける対数の底は、一般的に 2 です（$\log_2 n$）。 これは、「データ量 $n$ を半分に割り続けると、何回で 1 になるか？」を意味します。

代表的な例が二分探索（Binary Search）です。ソート済みの配列から特定の要素を探す際、中央の値と比較して探索範囲を半分ずつに絞り込んでいきます。データ量が $1,000,000$ あっても、約 20 回の比較で見つけることができるという、非常に強力なアルゴリズムの背後には、この対数の性質があります。

3. 漸化式と数列

ある項がそれ以前の項を用いて定義される数式のことを漸化式と呼びます。

再帰関数と動的計画法

漸化式は、プログラミングにおける再帰関数（Recursive function）に直結します。 例えば、フィボナッチ数列（$F_n = F_{n-1} + F_{n-2}$）は、そのまま再帰関数として実装できます。

さらに、再帰呼び出しの無駄な計算（同じ引数に対する重複計算）を省くために計算結果を配列に記憶しておく手法がメモ化（Memoization）であり、それをボトムアップに行うのが動的計画法（Dynamic Programming; DP）です。動的計画法で最適解を導き出す過程は、漸化式を解いているのと同じ状態と言えます。

4. グラフ理論

ここで言う「グラフ」は、棒グラフや折れ線グラフではなく、「頂点（ノード）」とそれを結ぶ「辺（エッジ）」で構成される構造のことです。

現実世界の多くの問題は、グラフとしてモデル化できます。

• 最短経路問題: カーナビのルート探索、ネットワークのルーティング。
• ソーシャルグラフ: SNS におけるユーザー間のフォロー関係。
• 依存関係の解決: パッケージマネージャにおけるライブラリの依存関係。

グラフを探索する代表的なアルゴリズムである 幅優先探索（BFS） や 深さ優先探索（DFS）、最短経路を求める ダイクストラ法 などを理解するベースとして、グラフ理論の基本的な用語を知っておく必要があります。

5. 確率と統計

データの分析や機械学習の分野に限らず、一般的なプログラミングでも確率論が役立つ場面は多いです。

• 乱数の生成と活用: ランダムに要素をシャッフルしたり、ゲームのガチャの確率を実装したりする際に、一様分布や正規分布といった確率分布の考え方が必要になります。
• モンテカルロ法: 乱数を用いてランダムなシミュレーションを多数回行い、円周率などの近似値を求める手法です。
• ハッシュ関数: ハッシュテーブルでデータの衝突（コリジョン）が起きる確率を抑えるための設計には、確率の知識が潜んでいます。

6. 行列と線形代数

一見すると複雑な数式の羅列に見える行列ですが、データを「多次元の配列」として扱うための強力なツールです。

• 3D グラフィックス: オブジェクトの回転、拡大縮小、平行移動などの座標変換は、すべて行列の掛け算によって計算されています。
• 機械学習とディープラーニング: 大量のデータを一度に処理（テンソル演算）するため、内部的には膨大な行列演算が行われています。

まとめ

アルゴリズムで使う数学は、決して机上の空論ではなく、「現実の問題をコンピュータに効率よく解かせるための道具」です。

• 論理を整理するための「離散数学」
• 効率化の威力を示す「対数」
• 複雑な問題を分割する「漸化式」
• 関係性を表現する「グラフ理論」

これらを完璧にマスターしてからプログラミングを始める必要はありません。プログラミングで壁にぶつかったときや、より効率的なアルゴリズムを学びたいときに、「そういえばこれはあの数学の概念だな」と紐づけて少しずつ学んでいくのが、最も実践的で楽しい学習方法だと思います。