はじめに
同じ結果を得るプログラムでも、データが少ない間は違いが見えず、件数が増えた途端に処理が重くなることがあります。このとき「何秒かかったか」だけを見ると、パソコンの性能や実装方法の違いが混ざり、処理の仕組みそのものを比べにくくなります。
計算量は、入力するデータの大きさに応じて、処理に必要な時間やメモリがどのように増えるかを捉える考え方です。この記事では時間計算量を中心に、Big O記法の意味とO(1)・O(n)・O(n²)の違いを整理し、入力サイズが大きくなったときに処理の差をどう考えればよいかを解説します。
計算量とは
計算量とは、問題や入力データの大きさに対して、アルゴリズムが必要とする計算資源の増え方を表す尺度です。代表的なものに、処理に必要な時間の増え方を見る「時間計算量」と、必要なメモリ量の増え方を見る「空間計算量」があります。この記事では、処理の効率を考える入口として時間計算量を中心に扱います。
計算量を考えるときは、入力サイズを一般に n で表します。例えば、100件のデータを順番に確認する処理ならn=100、1,000件ならn=1,000です。処理の流れそのものを整理したい場合は、先に「制御構造とは？順次・分岐・反復の3つをわかりやすく解説」を確認すると、どこで処理回数が増えるのかを追いやすくなります。
Big O記法で増え方を表す
Big O記法は、入力サイズnが十分大きくなったときに、処理量の増え方を上限側から捉える記法です。厳密には「漸近的な上界」を表しますが、ここでは入力が増えたときの増加傾向を比較するための記法として捉えます。実務や学習では、定数倍や小さい次数の項をいったん外し、処理量が主にどのような形で増えるかを比較するために使います。
例えば、処理回数が「3n+10」のように増える場合、nが大きくなるほどnに比例する部分が支配的になるため、通常はO(n)として増え方を整理します。Big Oは実行時間を秒で予測するものではなく、入力が増えたときに処理量がどのようなペースで増えるかを見るためのものです。
O(1)・O(n)・O(n²)の違い
プログラミングの基礎で最初に押さえたいのは、入力サイズが増えても処理量がほぼ変わらないO(1)、入力サイズに比例して増えるO(n)、入力サイズの二乗に近い形で増えるO(n²)です。次の表は、増え方の違いを単純化して比較したものです。
| 記法 | 増え方の目安 | n=10の例 | n=1,000の例 | 処理のイメージ |
|---|---|---|---|---|
| O(1) | 一定 | 1 | 1 | 入力件数に関係なく、決まった回数の処理で終わる |
| O(n) | nに比例 | 10 | 1,000 | データを先頭から1件ずつ確認する |
| O(n²) | nの二乗に比例 | 100 | 1,000,000 | 各データについて全データを確認する |
表の数値は増え方を理解するための単純化した例であり、実際の命令数や実行時間を表すものではありません。重要なのは、nが10倍になったとき、O(n)なら処理量もおおむね10倍ですが、O(n²)ではおおむね100倍へ広がるという違いです。
入力サイズが増えると差が広がる
入力が小さいうちは、O(n)とO(n²)の処理でも実行時間に大きな差が見えないことがあります。しかし入力サイズが増えるほど、増加率の違いが効いてきます。n=100ならn²は10,000ですが、n=10,000ならn²は100,000,000となり、同じ処理の繰り返し方でも必要な処理量は急激に増えます。
そのため計算量は、「今のデータ量で速いか」だけではなく、「データ量が増えたときにも現実的な時間で処理できそうか」を考える材料になります。小さなテストデータで問題がなくても、本番データで遅くなる場合は、入力サイズに対して処理量がどのように増えているかを確認することが重要です。
計算量だけで実行速度は決まらない
同じO(n)の処理でも、1件あたりに行う仕事が違えば実際の実行時間は変わります。プログラミング言語や実装方法、CPU・メモリ、キャッシュ、入出力、データの特徴なども影響するため、Big Oが小さい処理が常に短時間で終わるとは限りません。
Big Oは、こうした実行環境の差をいったん離れて、入力サイズが大きくなったときの増え方を比較するための尺度です。アルゴリズムの選択では計算量を確認し、実際の性能が重要な場面では計測結果も合わせて判断する、という役割分担で考えると理解しやすくなります。
二重ループの改善につなげる
二重ループでは、外側の処理をn回、内側の処理もn回繰り返すなら、処理回数はおおむねn×nとなり、O(n²)として捉えられます。ただし、二重ループだから必ずO(n²)になるわけではありません。内側の回数が固定なら全体はO(n)になる場合があり、外側がn件・内側が別の入力サイズm件ならO(nm)と考える方が適切です。
重要なのはループの見た目だけで判断せず、入力サイズに応じて各処理が何回実行されるかを数えることです。処理量が大きいと分かったら、同じ検索を何度も行っていないか、事前に整理したデータを利用できないか、ループ内で変わらない計算を外へ出せないかを確認します。具体的な見直し方は、「二重ループを高速化するには？処理量とデータ構造の見直し方」で解説しています。
まとめ
計算量は、入力サイズが増えたときに、処理時間や必要な資源がどのように増えるかを考えるための尺度です。時間計算量では、Big O記法を使って増加傾向を整理し、O(1)・O(n)・O(n²)のように処理量の伸び方を比較できます。
Big Oは実行秒数そのものではなく、入力が大きくなったときの増え方を見るためのものです。処理の繰り返し回数を入力サイズと結び付けて考えられるようになると、二重ループなど処理量が増えやすい箇所を見つけ、改善の必要性を判断しやすくなります。
関連記事
