LASSIC Media らしくメディア
計算量とは？オーダー記法(Big-O)の基本
LASSIC IT事業部｜元請（プライムベンダー）としてシステム開発・検証を受託
システムの設計レビューや見積もりの場で、「この処理の計算量はどのくらいですか」という話題が出て、実装担当ではない企画担当の方が戸惑う場面があります。検証環境の少ないデータでは問題なく動いていた処理が、本番でデータ量が増えた途端に応答が重くなる、というトラブルは珍しくないものです。原因の多くは、設計段階でその処理の計算量を見積もっていなかったことにあります。
特に企画担当者にとっては、要件定義の段階で「将来どのくらいの件数を扱う想定か」を開発チームと共有できているかどうかが、後々の性能問題を左右する分かれ目になりやすいものです。
本記事では、計算量とは何か、そしてオーダー記法（Big-O）の読み方を、特定の言語やライブラリの優劣には立ち入らず、法人のIT部門担当者向けに整理します。数式は最小限にとどめ、押さえておきたい考え方の骨格に焦点を当てます。
この記事のポイント
- 計算量とは、データ量nに対して処理時間やメモリ使用量がどれだけ増えるかを表す指標で、時間計算量と空間計算量の2つに分けて捉える考え方です。
- オーダー記法（Big-O）はO(n)やO(n²)のように増加の傾向を大まかに表す記法で、定数項や低次の項を無視し、最悪の場合を基準とする考え方です。
- 全件探索はO(n)、二分探索はO(log n)といった違いを把握しておくと、データ量が増えたときのスケーラビリティを見積もる材料になります。
計算量とは何か
計算量とは、処理対象のデータ量（一般にnという文字で表します）が増えたときに、処理時間やメモリ使用量がどれだけ増加するかを表す考え方です。実際の秒数やバイト数を測るものではなく、「データが2倍、10倍になったときに、処理量がどのくらいの割合で増えるか」という増加の傾向を捉える指標だと考えると分かりやすいでしょう。
時間計算量と空間計算量
計算量は大きく2つに分けられます。時間計算量は、処理にかかるおおよそのステップ数がデータ量に対してどう増えるかを表すものです。一方の空間計算量は、処理の途中で必要になるメモリやストレージの使用量がデータ量に対してどう増えるかを表します。両者はトレードオフの関係になる場面もあり、処理速度を優先して一時的なメモリ使用量を増やす設計と、メモリを節約するために計算をやり直す設計とのどちらを取るかが問われることもあるでしょう。
なぜ「データ量n」を主語に考えるのか
計算量の議論では、扱うデータの件数を一般化して「n件」と表現し、nが大きくなったときにどうなるかを主語に考えます。検証環境で扱うデータが数百件であれば問題にならない処理でも、本番環境で数百万件を扱うようになった途端に処理時間が跳ね上がる、という事態は珍しくないものです。設計段階で「このnが将来どこまで増える見込みか」を意識しておくことが、計算量を考える出発点になります。
なぜ計算量が重要なのか
計算量を意識する意義は、実装後の性能問題を未然に防げる点にあります。代表的な理由を整理しましょう。
データが増えたときの性能を見積もれる
計算量を把握しておくと、データ量が増えたときに処理時間がどの程度伸びるかを、実装前の段階である程度見積もれるようになります。O(n)の処理であればデータが10倍になれば処理量もおおよそ10倍、O(n²)の処理であれば理論上100倍近い増え方をするという違いを把握しているだけでも、将来のデータ量を見据えた設計判断がしやすくなります。
非機能要件の判断材料になる
レスポンスタイムやスループットといった非機能要件を検討する場面でも、計算量は判断材料の一つです。特定の処理がO(n²)に近い性質を持つと分かっていれば、想定される上限に近いデータ件数を早い段階で確認し、件数が一定を超える場合は設計を見直すといった対応を事前に検討できます。性能問題が本番運用で発覚してから対処するより、設計段階で見積もっておくほうが手戻りを抑えやすいものです。
計算量は設計と保守のコストにも関わる
計算量を軽視した設計は、性能問題だけでなく、保守のしやすさにも影を落とすことがあります。データ件数が増えるたびに、対症療法的にサーバーの台数やスペックを増やして処理時間の悪化をしのぐ運用を続けていると、根本の処理構造を見直すタイミングを逃し、改修コストが膨らみやすくなります。設計の初期段階で計算量に見合った実装を選んでおくことは、後から発生しうるインフラ増強のコストを抑える判断にもつながるものです。
オーダー記法（Big-O）の読み方
計算量を表す代表的な記法が、O（オー）を使ったオーダー記法（Big-O記法）です。O(n)やO(n²)のような表記を目にしたことがある方も多いでしょう。ここでは代表的なオーダーの読み方を整理します。
代表的なオーダーの種類
オーダー記法では、データ量nに対して処理量がどう増えるかを大まかな式で表します。細かい係数や影響の小さい低次の項は無視し、データ量が大きくなったときに支配的になる増加の傾向だけを捉える考え方です。
| 表記 | 読み方 | 増加の傾向 | 身近な例 |
|---|---|---|---|
| O(1) | 定数時間 | データ量に関わらずほぼ一定 | 配列の特定位置への直接アクセス |
| O(log n) | 対数時間 | データが増えても増え方は緩やか | 整列済みデータへの二分探索 |
| O(n) | 線形時間 | データ量にほぼ比例して増える | 先頭から順に確認する全件探索 |
| O(n log n) | 線形対数時間 | 線形よりやや大きいが二乗よりずっと緩やか | 効率的な整列（ソート）処理 |
| O(n²) | 二乗時間 | データ量の2乗に近い勢いで増える | 二重ループでの全組み合わせ確認 |
最悪計算量という考え方
オーダー記法で語られる計算量は、多くの場合「最悪計算量」、つまり条件が厳しいケースを想定した見積もりを指します。探索処理であれば、探している値が末尾にある、あるいは存在しない場合が最悪のケースにあたるでしょう。平均的なケースでは速く終わる処理でも、最悪計算量が大きい場合はその可能性を踏まえておく必要があります。データの並び順や入力の傾向に左右されにくい見積もりとして、最悪計算量を基準に考える場面が多い点は押さえておきたいところです。
次の図は、データ量nが増えていったときに、代表的なオーダーごとに処理量がどのように伸びていくかを、イメージとして示したものです。
身近な例で理解する計算量
抽象的な説明だけでは実感が湧きにくいため、身近な処理を例に、オーダーの違いを具体的に見ていきましょう。
全件探索O(n)と二分探索O(log n)
並んでいないリストから特定の値を探す場合、先頭から順に一件ずつ確認していく全件探索はO(n)の計算量になります。データが1万件から10万件に増えれば、最悪の場合の確認回数もおおよそ10倍に増える計算です。一方、あらかじめ昇順などに整列されたデータであれば、中央の値と比較して探索範囲を半分に絞り込んでいく二分探索が使え、この場合の計算量はO(log n)になります。データが10万件でも、二分探索なら確認回数は十数回程度で済み、データ量が増えても確認回数の増え方は緩やかです。ただし二分探索を使うには、事前にデータが整列されている必要がある点には注意しましょう。
ネストしたループがO(n²)になりやすい理由
二重ループの内側でもう一度全件を確認するような処理は、O(n²)になりやすい典型例です。n件のデータから重複する組み合わせをすべて洗い出す処理を単純な二重ループで書くと、外側のループがn回、内側のループもそれぞれn回動くため、処理量はおおよそn×n、つまりn²に近い増え方をします。データ件数が少ないうちは体感できる差になりませんが、件数が数万件を超えたあたりから処理時間が急激に伸び、画面のタイムアウトやバッチ処理の遅延として表面化する場合があるでしょう。
キーで直接引き当てる検索がO(1)に近づく理由
会員番号や商品コードのようなキーを使い、ハッシュ構造でデータを保持しておく仕組みでは、検索がO(1)に近い性質を持つ場合があります。キーから保存場所をおおよそ一意に導き出せるため、件数が増えても照合にかかる手間が大きく変わりにくいことが理由です。ただしキーの衝突が多い設計や、キーの分布に偏りがある場合には、想定していたほどの効果が得られないこともあり、万能の解決策ではない点は留意しておきたいところです。
実務での活かし方
件数が増える前提で設計する
システムを新規に設計する際は、現在のデータ件数だけでなく、運用開始から数年後にどの程度の件数まで増える見込みかを関係者と共有しておくことが、計算量を意識した設計の第一歩になります。データ量が将来数十倍に増える可能性があるなら、O(n²)に近い処理を含む設計は、早い段階で見直しの対象にしておくとよいでしょう。
DBインデックスやアルゴリズム選択が効いてくる場面
データベースのインデックス設計も、計算量の考え方と深く関わっているものです。インデックスが設定されていない列に対する検索は、実質的に全件確認に近いO(n)の処理になりがちですが、適切なインデックスを設定すれば、二分探索に近い効率での検索が可能になります。件数が少ないうちは体感しにくい差でも、テーブルの行数が増えるにつれて、インデックスの有無による応答時間の差は大きく開いていく傾向があります。ソートやフィルタリングを自前で実装する場合も、標準的に用意された効率のよい機能を活用できないか検討する価値があるでしょう。
過度な最適化を避けるバランス感覚
一方で、扱うデータ件数が今後も少数にとどまる見込みの処理にまで、無理に計算量を切り詰めた実装を追求する必要はありません。可読性やメンテナンス性を犠牲にしてまで複雑な実装を選ぶと、かえって改修時のリスクを高めてしまいます。計算量はあくまで判断材料の一つであり、「このnはどこまで増えるか」を見極めたうえで、必要な箇所に絞って効率を意識するバランス感覚が実務では求められるものです。
応答時間の推移を監視し、兆候を早めにつかむ
設計段階での見積もりに加えて、運用開始後もデータ件数の増加と応答時間の関係を継続的に観測しておくと、O(n²)に近い性質を持つ処理の兆候を早い段階でつかみやすくなります。件数の増加に比例せず応答時間が急に伸び始めた処理があれば、その処理の計算量を疑ってみる価値があるでしょう。監視の仕組みを通じて件数と応答時間の推移を可視化しておくことは、設計段階の見積もりを裏付ける材料にもなります。
まとめ：計算量を設計判断に活かす
本記事では、計算量とは何か、時間計算量と空間計算量の違い、オーダー記法（Big-O）による代表的な増加パターンの読み方、そして身近な処理を例にした具体的なイメージまでを整理しました。計算量は、データ量が増えたときの性能やスケーラビリティを見積もるための、実装前に確認しておきたい判断材料です。
特定の言語やアルゴリズムの優劣を断定するものではなく、あくまで「増加の傾向をあらかじめ把握しておく」という考え方の骨格として活用いただければと思います。自社で扱うデータ量が将来どこまで増える見込みか、そしてその処理がどのオーダーに近い性質を持つのか、この機会に確認してみてはいかがでしょうか。
企画担当者と開発担当者が計算量という共通の物差しを持てると、非機能要件の合意形成もスムーズになります。要件定義の段階から「想定件数」と「許容できる応答時間」を数値で共有しておく習慣が、結果として手戻りの少ない開発につながっていくはずです。
よくある質問
計算量とプログラムの実行速度は同じ意味ですか。
厳密には異なる概念です。計算量はデータ量の増加に対する処理量の増え方の傾向を表す指標であり、ハードウェアの性能や実装の細部による実際の実行速度そのものを表すものではありません。同じ計算量の処理でも、実装や環境によって実際にかかる時間は変わってきます。
O(n)とO(n²)の違いはどのくらい大きいですか。
データ量が増えるほど差は開いていきます。データが100件であればO(n)は100、O(n²)は1万という計算になり、データが1万件に増えるとO(n)は1万、O(n²)は1億に近い数値になります。件数が少ないうちは体感しづらい差ですが、件数が増えるにつれて無視できない開きになっていくものです。
空間計算量はどのような場面で意識すればよいですか。
扱うデータ量に対してメモリやストレージの制約が厳しい環境で処理を実装する場合や、一時的に大量のデータを保持する処理を設計する場合に意識する価値があります。処理速度を優先して一時データを多く保持する設計と、メモリを節約して計算をやり直す設計は、トレードオフの関係になりやすい点も押さえておくとよいでしょう。
計算量を意識すると実装が複雑になってしまいますか。
計算量のよい実装が常に複雑になるとは限りません。既存の効率的なアルゴリズムやライブラリの機能を活用するだけで、計算量を改善できる場面も多くあります。件数が少ない処理にまで無理に最適化を追求する必要はなく、影響の大きい箇所を見極めて対応することが実務的なバランスといえるでしょう。
非エンジニアの担当者も計算量を理解しておいたほうがよいですか。
実装の細部まで理解する必要はありませんが、「データが増えると処理時間がどう変わりそうか」という大まかな傾向を把握しておくと、開発チームとの会話や非機能要件の検討がスムーズになります。将来のデータ量の見込みを共有することも、非エンジニアの担当者が担える役割の一つです。
著者：テレリモ総研編集部 鈴木 亮佑
ご不明な点はお問い合わせフォームからもご連絡いただけます。
- *1 出典：フリー百科事典『ウィキペディア』「O記法」（https://ja.wikipedia.org/wiki/O記法）
- *2 出典：フリー百科事典『ウィキペディア』「計算複雑性理論」（https://ja.wikipedia.org/wiki/計算複雑性理論）
