オーダー記法

オーダー記法は、入力サイズnが大きくなるときの計算時間又は記憶量の増え方を、定数倍や低次項を除いて漸近的に表す記法です。

■ 試験で押さえるポイント

• $O(f(n))$は十分大きなnで処理量が定数倍のf(n)以下となる上界、Ωは下界、Θは上下から同じ次数で挟む厳密な増加率を表します。

• 一般的な増加の速さは$O(1)$、$O(\log n)$、$O(n)$、$O(n\log n)$、$O(n^2)$、$O(2^n)$、$O(n!)$の順に急になります。

• $3n^2+5n+100$は最高次項が支配するため$O(n^2)$です。係数3や低次項を無視しても、実測時間が同じという意味ではありません。

• オーダーと最悪・平均・最良の場合は別の軸です。「クイックソートは$O(n\log n)$」のような記述では、どの場合かも確認します。

■ 選択肢での判断ポイント

逐次処理は和、入れ子の独立ループは積として回数を数え、最高次項だけを残します。OとΘを厳密に問う問題にも注意します。

例: 処理回数$T(n)=2n^2+10n+3$なら、n増大時はnの2乗項が支配するので$O(n^2)$です。nを2倍にすると支配項は約4倍になります。