計算量のオーダー表記とは
計算量のオーダー表記（O記法／オー記法）とは、アルゴリズム（問題を解く手順）の効率の良さを評価するために、処理を実行するのに必要な手間や時間が、処理するデータの量（N）が増えたときにどれくらい増加するかを大まかに表す記法です。
コンピュータの性能や実行環境に関わらず、アルゴリズムそのものの純粋な「賢さ」を測るために使われます。データの数Nに対して、処理回数が比例して増える場合は「O(N)」、データの数の2乗で増える場合は「O(N^2)」のように表記します。Oの中の式が小さいほど、データ量が増えても遅くなりにくい、効率の良い優れたアルゴリズムであることを意味します。
具体例
本棚から特定の1冊の本を探す場面を考えます。端から順番に1冊ずつ探す方法（線形探索）では、本がN冊あると最大でN回の確認が必要なため、計算量は「O(N)」になります。一方、辞書のようにあいうえお順に並んでいる本棚で、真ん中を開いて前後を絞り込んでいく方法（二分探索）では、回数は大幅に減り「O(log N)」となり、本が大量になっても一瞬で見つけ出すことができます。
もう少し詳しく
O記法（ビッグオー記法）は、データ量Nが無限に大きくなったときの「最悪の場合の処理効率」の上限を示すために用いられます。そのため、定数倍の差や影響の小さい低次の項は無視されます。例えば、正確な処理ステップ数が「3N^2 + 5N + 10」であるアルゴリズムの場合、Nが非常に大きくなると「N^2」の項が全体を支配するため、他の部分は省略して「O(N^2)」と表記します。計算量には、処理時間を示す「時間計算量」と、実行に必要なメモリスペースを示す「領域（空間）計算量」の2種類があります。一般に、メモリを多く使ってあらかじめデータを記録しておくことで処理時間を短縮するなど、時間と空間の間にはトレードオフが存在することが多く、システム要件に合わせて使い分けることが求められます。
試験でのポイント
試験では、代表的なアルゴリズムの計算量を暗記・判定する問題がよく出題されます。例えば、二分探索は「O(log N)」、バブルソートや挿入ソートは「O(N^2)」、マージソートやクイックソート（平均）は「O(N log N)」であることなどが定番です。また、「データ数が10倍になったとき、処理時間は何倍になるか」という応用計算問題も頻出します。「O(N)」であれば10倍ですが、「O(N^2)」であれば100倍、「O(log N)」であれば数倍（底が2の場合）になります。数式の計算特性を理解し、Nの増加に対して各オーダー（O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N)）がどのような順序で大きくなるかを頭に叩き込んでおきましょう。
関連する用語
計算量のオーダー表記に関連する用語としては、最も基本的なデータの探索手法である「線形探索（O(N)）」や「二分探索（O(log N)）」があります。また、処理効率を劇的に向上させるための並べ替え手法である「クイックソート（O(N log N)）」や、計算量は多いが単純な「バブルソート（O(N^2)）」、そして時間計算量とトレードオフの関係にある「領域（空間）計算量」も重要な関連概念です。