アルゴリズムの計算量を理解する（後半）
前半では、計算量の「増え方の感覚」を中心に、 O(1)・O(n)・O(n²)・O(log n) といった基本的な時間計算量を Java の例で整理しました。 後半では、より実務寄りの視点として ソートの計算量、再帰と計算量の関係、 そして 計算量とセキュリティ（DoS攻撃）、最後に アルゴリズム選択の判断基準 を深掘りします。
計算量は「数学の記号」ではなく、 読者が 現場でコードを書くときの判断力 を育てるための道具です。 その視点を軸に、後半を進めていきます。
ソートアルゴリズムの計算量を理解する（Javaでの具体例）
ソートは計算量を学ぶうえで最も良い教材です。 なぜなら、アルゴリズムによって「増え方」が劇的に変わるからです。
バブルソート（O(n²））
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
二重ループなので、計算量は O(n²)。 要素数が増えると、処理時間が爆発的に増えます。
10 → 100 回 100 → 10,000 回 1000 → 1,000,000 回
この「増え方の違い」が計算量の本質です。
高速ソート（O(n log n））のイメージをつかむ
Java の Arrays.sort() は、内部で TimSort（マージソート＋挿入ソートのハイブリッド）を使っています。 計算量は平均 O(n log n) です。
なぜ O(n log n) が速いのか
log n の増え方は非常にゆるやかです。
n = 1,000 → log₂n ≈ 10 n = 1,000,000 → log₂n ≈ 20
つまり、要素数が 1000 倍になっても、 「半分に分割する回数」は 10 回しか増えません。
この「分割して処理する」という発想が、 高速ソートの計算量を O(n log n) に抑えています。
再帰と計算量の関係を深掘りする
再帰は美しく書けますが、計算量を意識しないと危険です。
フィボナッチの再帰（O(2ⁿ））
public static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
このコードは、入力が少し増えただけで処理時間が爆発します。
n = 30 → 数百万回 n = 40 → 数億回 n = 50 → 数十億回
これは「同じ計算を何度も繰り返す」ためです。
メモ化や DP にすると O(n）になる
public static int fibDP(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
計算量は O(n)。 増え方が劇的に改善されます。
ここで重要なのは、 再帰は「構造が美しい」だけで、計算量が良いとは限らない という点です。
計算量とセキュリティ（DoS攻撃の観点）
計算量は「性能」の話だけではありません。 セキュリティスペシャリストの視点では、 計算量は 攻撃者が悪用できる弱点 になります。
危険な例：入力によって計算量が爆発するコード
public static int fibDanger(int n) {
if (n <= 1) return n;
return fibDanger(n - 1) + fibDanger(n - 2);
}
攻撃者が n = 50 のような値を送ると、 サーバーは膨大な計算を強制され、応答不能になります。
これは典型的な DoS（サービス妨害）攻撃 の入り口です。
安全にするための対策
入力の上限を設ける 計算量が悪いアルゴリズムを使わない メモ化や DP を使って計算量を改善する タイムアウトやキャンセル処理を設ける
計算量を理解することは、 「安全なコードを書く」ためにも必須です。
実務でのアルゴリズム選択の判断基準
計算量を理解すると、次のような判断ができるようになります。
データ量が小さいなら「読みやすさ」を優先
例えば 100 件程度なら、O(n²) のアルゴリズムでも問題ありません。 コードのシンプルさが優先されます。
データ量が大きいなら「計算量」を最優先
ログ解析、検索、機械学習などでは 数万〜数百万件のデータを扱うため、 O(n log n) や O(n) のアルゴリズムが必須になります。
入力がユーザー依存なら「安全性」を優先
攻撃者が入力を操作できる場合、 計算量が爆発するアルゴリズムは絶対に使ってはいけません。
計算量を自分のものにするための最終ポイント
計算量は「暗記するもの」ではなく、 コードを書きながら自然に身につけるものです。
そのためには、次の三つを意識すると効果的です。
どれくらいループが回るかを数える
一重ループ → O(n) 二重ループ → O(n²) 半分に分割 → O(log n)
再帰の「呼び出し回数」をイメージする
フィボナッチのように「枝分かれ」する再帰は危険。
データ量が増えたときの「増え方」を想像する
10 件 → 100 件 → 1000 件 この増え方を頭の中で描けるようになると、計算量が理解できてきます。
後半のまとめ
後半では、計算量を実務レベルで使いこなすための内容を扱いました。
ソートの計算量（O(n log n) と O(n²) の違い） 再帰と計算量の関係（危険な O(2ⁿ）） 計算量とセキュリティ（DoS攻撃） アルゴリズム選択の判断基準
計算量を理解すると、 「どのアルゴリズムを選ぶべきか」を自信を持って判断できるようになります。