「計算量って何？」
応用情報技術者試験でもアルゴリズム分野で超頻出ですが、

O(n)？
O(log n)？
何を表してる？
なぜ重要？

で混乱する人がかなり多いテーマです。

この記事では、

計算量とは？
O記法
代表的な計算量
試験での頻出ポイント

を5分で理解できるように解説します！

まず結論

計算量とは？

「処理量の増え方」

です！

超簡単にいうと

データ量が増えた時、

どれくらい重くなるか

を表す。

なぜ重要？

例えば：

10件なら速い
100万件なら激遅

では困る！

だから

効率の良いアルゴリズム

が必要。

引っ越しで理解しよう

かなり分かりやすい👇

荷物10個

すぐ終わる。

荷物1万個

超大変！

計算量とは

「荷物増加で作業量がどう増えるか」

みたいなもの。

O記法とは？

超頻出！

書き方

O(n)

など。

読み方

オーダー記法

または：

ビッグオー記法

nとは？

データ数

O(n)

意味

データ数に比例

例

線形探索。

1件 → 1回
100件 → 100回

O(n²)

超頻出！

意味

二乗で増える

例

100件 → 10000

かなり重い！

代表例

バブルソート
選択ソート

O(log n)

超重要！

意味

少しずつしか増えない

例

二分探索。

イメージ

毎回半分に減る

100万件でも：

約20回程度。

超高速！

O(n log n)

高性能ソートで多い

代表👇

クイックソート
マージソート

計算量比較

超重要！

計算量	速さ
O(1)	超高速
O(log n)	高速
O(n)	普通
O(n log n)	実用高速
O(n²)	遅め

O(1)とは？

データ数関係なし

例

配列アクセス。

A[5]

なぜ？

場所がすぐ分かる。

実行時間との違い

ここ混乱しやすい！

計算量

増え方

実行時間

実際の秒数

つまり

PC性能で秒数は変わる。

でも：

計算量はアルゴリズムの性質

応用情報で超頻出

かなり狙われる👇

O(n)
O(log n)
O(n²)
二分探索
ソート

よくあるひっかけ

「O(n²)はn×2」

→ 違う！

nの二乗

1分で復習！

計算量

処理量増加の大きさ

O(n)

比例増加

O(log n)

少ししか増えない

O(n²)

急増加

練習問題

問題

二分探索の計算量として最も適切なものはどれか。

ア

O(1)

イ

O(log n)

ウ

O(n)

エ

O(n²)

解答

正解：イ

解説

二分探索は探索範囲を毎回半分に減らすため、計算量はO(log n)となります。

まとめ

計算量とは

「処理量の増え方」

超重要

O(log n)
O(n)
O(n²)
O(n log n)

まずは、

「logは高速」

「n²は重い」

このイメージを持つとかなり理解しやすくなります！

リンク一覧（5分で理解）はこちら

知識に自信ができた方は、今度は自身のキャリアアップに向けて準備してみませんか？

未経験から、ITエンジニアへ。

「IT業界に興味はあるけれど、自分にできるか不安」「何から始めればいいのか分からない」そんな方のために、Tech GO は未経験からのIT転職を専門的にサポートします。求人を紹介するだけではなく、あなたの強みを整理し、応募準備から入社後の成…

まずは無料でキャリア相談