計算量とは
計算量（けいさんりょう）とは、コンピュータがあるプログラムを実行する際に、どれだけの「時間」や「メモリの量」を必要とするかを表す指標です。プログラムの性能や効率の良さを測るために使われます。データ数が多くなったときに、処理にどれくらい時間がかかるかを示すものを「時間計算量」、どれくらいメモリを消費するかを示すものを「領域計算量」と呼びます。計算量は一般的に「O記法（オー記法）」を用いて「O(N)」や「O(N^2)」のように表記されます。Nは処理するデータの数です。この値が小さいほど、データが増えても高速に動作する優れたプログラムであると判断できます。
具体例
例えば、本棚から特定の1冊の辞書を探す場合を考えます。端から順番に1冊ずつ探す方法（線形探索）では、本がN冊あると最大でN回の確認が必要です。この場合の計算量は「O(N)」と表されます。一方で、辞書が五十音順に並んでいることを利用して、真ん中のページを開いて半分ずつ絞り込んでいく方法（二分探索）では、最大でも「O(log N)」という非常に少ない回数で探し出すことができます。
もう少し詳しく
計算量を考える上で欠かせないのが「O記法（ビッグオー記法）」です。これは、データの数 N が非常に大きくなったときに、計算時間がどれくらい急激に増加するかの「最悪の場合のオーダー（規模）」を示すものです。代表的な計算量には、データ量に関わらず一定の時間で終わる O(1)、データ量に比例して時間が増える O(N)、二分探索のようにデータが増えても時間が少ししか増えない O(log N)、そして二重ループのようにデータ量の2乗に比例して時間が爆発的に増える O(N^2) などがあります。実際の開発現場では、扱うデータが数万件、数百万件となることが珍しくありません。このような大規模なデータを扱う場合、O(N^2) のアルゴリズムでは処理に数時間かかってしまうものが、O(N log N) のアルゴリズムを採用するだけで数秒で完了するほど劇的な差が生まれます。そのため、アルゴリズムを選択する際には常に計算量を意識することが不可欠です。
試験でのポイント
情報処理技術者試験では、与えられたプログラムやアルゴリズムの計算量（特に時間計算量）を答えさせる問題が定番です。試験対策のポイントとしては、まずループの構造に注目することです。単純な1重ループなら O(N)、ループの中にさらにループがある2重ループなら O(N^2) となるのが基本です。ただし、ループの増え方が半分ずつになっていくような処理（二分探索など）では O(log N) となることを見抜けるようにしておきましょう。また、アルゴリズムの性能を評価する際に、「最良の場合」「平均の場合」「最悪の場合」の計算量の違いを問われることもあります。例えば、クイックソートは平均的には O(N log N) で非常に高速ですが、最悪の場合は O(N^2) になるという特徴は、試験でよく狙われる知識です。
関連する用語
計算量を評価する代表的なアルゴリズムとして、線形探索や二分探索などの探索アルゴリズム、そしてデータを規則に従って並べ替えるソートアルゴリズム（バブルソートやクイックソートなど）の計算量の違いを比較できるようにしておきましょう。