アルゴリズムの計算量（オーダ記法・O 記法）は、IPA 午前四択や基本情報の科目 B で繰り返し問われる定番です。最大のつまずきは『ループ構造からオーダをどう見積もるか』『なぜ O(log n) が出てくるのか』『オーダ同士の大小をどう比較するか』の 3 点です。型として整理すれば、暗記と見積りの両面から確実に得点できます。
出発点は O 記法の意味です。O 記法は、入力サイズ n が大きくなったときに処理量がどう増えるかだけを表し、定数倍や低次の項は無視します。代表的なオーダは、O(1)（定数時間・配列の添字アクセス）、O(log n)（対数時間・二分探索）、O(n)（線形時間・線形探索）、O(n log n)（マージソートやクイックソートの平均）、O(n²)（二重の入れ子ループ・選択／バブルソート）、O(2ⁿ)（指数時間）です。大小関係は O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²) ＜ O(2ⁿ) の順で、これを覚えておくと選択肢の比較が一瞬で済みます。
次はループ構造からの見積りです。基本は『ループが何回まわるかを数える』こと。1 重ループで n に比例して回るなら O(n)、二重の入れ子ループで内側も n 回まわるなら O(n²) です。1 回ごとに探索範囲が半分になる（二分探索のような）処理は O(log n)、半分に分割しながら全体を走査する処理は O(n log n) になります。『入れ子は掛け算、半分にするたびに log』と覚えると、コードを見て即座にオーダを判定できます。
仕上げは代表アルゴリズムの計算量の暗記です。探索では、線形探索が O(n)、二分探索が O(log n)（ソート済みが前提）、ハッシュ表の探索が平均 O(1) です。整列では、選択・バブル・挿入ソートが O(n²)、マージソートとヒープソートが O(n log n)、クイックソートは平均 O(n log n)・最悪 O(n²) です。これらは出題頻度が高く、値を覚えているだけで解ける問題が多いので、表にして暗記しておくと得点に直結します。
練習問題: n 個の要素について二重の入れ子ループですべてのペアを調べるアルゴリズムの計算量はいくつでしょうか。また、要素数が 1,000 から 2,000 へ倍に増えたとき、処理時間はおよそ何倍になるでしょうか。過去問AI の AI コパイロットに『この計算量の問題の解き方を教えて』と聞くと、ループ構造の数え方からオーダの大小比較まで手順がステップごとに表示されます。