計算量とオーダー記法

イントロ

計算や記法の入口をつくる

基本情報技術者試験で扱う「計算量とオーダー記法」を、IT知識なしでも意味と使いどころから学べるように整理します。まず目的をつかみ、似た言葉や条件の違いを短く見分けます。

定義

公式

計算・記法を、問題文の条件に当てはめて読む。

オーダーの読み方

T(n)=O(n log n)

入力件数nが増えたとき、処理時間の増え方を上から大まかに表します。

使うときのコツ

定数倍や低次の項より増え方を見ます。

増え方の目安

O(1)<O(log n)<O(n)<O(n²)

右へ行くほど大きな入力で重くなりやすい、代表的な増加順です。

使うときのコツ

小さい入力だけで速さを判断しないようにします。

解くコツ

入力サイズnが増えたとき、処理回数がどう増えるかを見る。単位、条件、対象範囲をそろえてから式や記法を使います。

例

場面: 件数が2倍になったとき、線形探索と2分探索で増え方が違う例
順に考えると: まずが何を表すかを確認します。次にオーダー記法との違いを、問題文の対象・条件・順序から分けます。ここでは入力サイズnが増えたとき、処理回数がどう増えるかを見る。
ここが結論: この例では、入力サイズnが増えたとき、処理回数がどう増えるかを見ることが要点です。答えを選ぶときは、オーダーが同じなら実行時間も常に同じだと思うという読み違いを避けます。

注意

確認

Q1

計算量とオーダー記法を問題で読むとき、最も適切な見方はどれですか。

まとめ