計算量を考える上で欠かせないのが「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) になるという特徴は、試験でよく狙われる知識です。
計算量を評価する代表的なアルゴリズムとして、線形探索や二分探索などの探索アルゴリズム、そしてデータを規則に従って並べ替えるソートアルゴリズム（バブルソートやクイックソートなど）の計算量の違いを比較できるようにしておきましょう。