計算量とオーダー記法

イントロ

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

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

定義

教科書では: 「計算量とオーダー記法」は、時間計算量、オーダー記法、O(1)などを手がかりに、基本情報技術者試験で何を見分けるかを整理するテーマです。
言いかえると: はじめて学ぶときは、まず「何のための言葉か」「何と混同しやすいか」を分けます。ここでは計算量とオーダー記法の定義、代表用語、基本的な読み方、簡単な適用判断を扱い、高度な実装、詳細な規格差、長い計算問題、特定製品の操作手順へ広げすぎません。そのうえで、時間計算量を単語として覚えるだけでなく、オーダー記法との違いを短く言える状態を目指します。

公式

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

オーダーの読み方

T(n)=O(n log n)

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

使うときのコツ

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

増え方の目安

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

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

使うときのコツ

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

解くコツ

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

例

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

注意

確認

Q1

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

まとめ