オーダー記法

オーダー記法は、入力のデータ数nが大きくなったときに、処理時間などがどのように増えるかを、O(n)のような形で大まかに表す記法です。

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

• 係数や低い次数の項は無視し、最も影響の大きい項だけを残します。

• 増え方は、O(1)＜O(log n)＜O(n)＜O(n log n)＜O(n²)＜O(2^n)の順に急になります。

• 二重のループは、一般にO(n²)になります。

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

最高次の項だけを残します。3n²＋5n＋100はO(n²)です。