数学科大学生が「時間計算量」を再考する

はじめに

こんにちは！
数学科の学部2年生のsebaと申します！
現在、株式会社ドクターズプライムでソフトウェアエンジニアのインターンをしており、主に Go, GraphQL, Hasura(PostgreSQL) などを触っています。

数学科にいると、プログラミングをしていても「理論的な背景」がどうしても気になってしまいます。今回は、私がインターンの技術試験で痛感した「時間計算量」について、数学科の視点（極限 $\lim$ の概念など）を交えつつ、実務でどう意識すべきかをまとめてみたいと思います。

---

技術試験での失敗：動くけれど「重い」コード

弊社の技術試験を受けた際、コーディングの問題が3問出題されました。
結果として試験自体は突破できたのですが、今振り返るとコードの質（時間計算量）は最悪でした。

この経験から、「ただ動くコード」と「エンジニアとして書くべきコード」の間には、時間計算量という大きな壁があることを学びました。

数学科視点で見る「オーダー記法」と $\lim$

エンジニアリングの世界では、計算量を表すのに $O(n)$ や $O(n^2)$ といった「ランダウの記号（ビッグオー記法）」を使います。

非理系の方や、数学から離れて久しい方のために説明すると、これは「データ量 $n$ が爆発的に増えたとき、処理時間がどういうカーブを描いて増えていくか（増加率）」を表す指標です。

なぜ $O(n)$ なのか？（極限の考え方）

数学科っぽく、これを極限（limit）の概念を使って考えてみます。

あるアルゴリズムの計算ステップ数が $f(n) = 3n^2 + 50n + 100$ だとします。
ここで $n$ が巨大になったとき（$n \to \infty$）、この式のそれぞれの項がどうなるかを見てみましょう。

たとえば $n = 1,000,000$（100万）を代入してみます。

• $3n^2$ の項： $3,000,000,000,000$ （3兆）
• $50n$ の項： $50,000,000$ （5000万）
• $100$ の項： $100$ （誤差レベル）

見ての通り、$n$ が大きくなればなるほど、$n^2$ の項があまりにも巨大になりすぎて、残りの $50n + 100$ はあってもなくても変わらない誤差になってしまいます。

数学の極限 $n \to \infty$ の世界では、「もっとも次数の高い項（ここでは $n^2$）」以外は、全て無視できるほどちっぽけな存在になります。
さらにオーダー記法では、「3兆」だろうが「1兆」だろうが「増え方のカーブ（放物線）」は変わらないため、係数の $3$ も無視します。

結果として、一番支配力を持っている「親玉」である $n^2$ だけを取り出して、$O(n^2)$ と書くわけです。これが計算量の見積もりの正体です。

グラフで見る「増加率」の恐怖

数式だけだとイメージしづらいかもしれないので、主要なオーダーの増加率をグラフで比較してみます。

グラフを見ると一目瞭然です。

• $O(1)$ や $O(\log n)$： 地を這うように緩やかです。データが増えても時間はほとんど増えません。
• $O(n)$： 直線的に増えていきます。
• $O(n^2)$： $n$ がある地点を超えた瞬間、二次関数的に急上昇します。これが私が技術試験で書いてしまったコードの正体です。
• $O(2^n)$： 指数関数です。あっという間に計算不能な領域に突入します。

学部2年生レベルの感覚で言うと、各オーダーの強さは以下のような力関係になります。

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$$

この「傾き」の違いは、サーバーの負荷やUXに直結します。

---

実務への落とし込み：GoとDBでの活用

ここからは、実際にインターンでの開発（Go, GraphQL, Hasura）において、この知識をどう意識しているかについて書きます。

1. アプリケーション層（Go）：二重ループを避ける

例えば、2つのスライス（リスト）を突き合わせて処理をする場面を考えます。
「ユーザー一覧」と「購入履歴一覧」があり、IDを元にマッチングさせたい場合です。

悪い例 ($O(n^2)$)

// ユーザーごとに全購入履歴を走査する
for _, user := range users {
    for _, order := range orders { // ここで二重ループ
        if user.ID == order.UserID {
            // 処理
        }
    }
}

これでは $n$ が増えると計算量が爆発します。グラフで言うところの急上昇カーブに乗ってしまいます。

改善例 ($O(n)$)：
ここで「Map（ハッシュマップ）」を使います。Mapへのアクセスは計算量が平均して $O(1)$ です。

// 先にOrderをMapにする（これがO(n)）
orderMap := make(map[int]Order)
for _, order := range orders {
    orderMap[order.UserID] = order
}

// Mapを参照する（これもO(n)）
for _, user := range users {
    if order, ok := orderMap[user.ID]; ok {
        // 処理（Mapの検索はO(1)なのでループ内で重くならない）
    }
}

このように、Mapというデータ構造を使うことで、数学的には $n^2$ の増加率を $n$ に落とすことができます。これは $n=10,000$ くらいの規模でも体感速度が劇的に変わります。

2. データベース層（Hasura/Postgres）：Indexと $O(\log n)$

Hasuraを使ってGraphQL APIを構築していると、データベースのパフォーマンスがそのままAPIのレスポンス速度になります。ここで重要なのが Index（インデックス）です。

通常、データベースから特定のデータを検索するとき、インデックスがないと Full Table Scan(全件走査)が行われます。これは $O(n)$ です。

しかし、Indexを貼ると、一般的にB-Treeなどの木構造が使われます。これにより検索計算量は $O(\log n)$ になります。

$O(\log n)$ の凄さ
数学科として $\log$ （対数）について語らせてください。
$\log_2 n$ は、$n$ が2倍になっても「+1」しか増えません。

• $n = 1,000$ のとき、探索回数は約10回
• $n = 1,000,000$ （100万）になっても、探索回数は約20回

データが1000倍になっても、計算時間はたった2倍にしかならない。これが $O(\log n)$ の圧倒的な強さです。
実務でも、「検索に使われるカラムには必ずIndexを貼る」という基本動作の裏には、この数学的な保証があるわけです。

おわりに

技術試験で「とりあえず動くコード」を書いてしまった反省から、改めて計算量について学び直しました。

数学科で習う $\lim$ や関数の増加率といった概念は、単なる数式遊びではなく、「ユーザーが増えてもサクサク動くアプリケーション」を作るための強力な道具です。
まだ学部2年生ですが、理論的な裏付けを持ちつつ、GoやHasuraを使ったモダンな開発で「強いコード」が書けるエンジニアを目指して精進します。