計算量とO記法をやさしく図解 — O(n)・O(log n)・O(n²)とは
「O(n) と O(log n) ってどっちが速いの？」——計算量は、データが増えたとき処理がどれだけ遅くなるかを表すモノサシです。細かい秒数ではなく「増え方の型」で比べるのがコツ。この記事では、代表的なオーダーを速い順に整理します。実際の速さの差を体感するなら 探索の可視化 や ソートの可視化 もどうぞ。
計算量とは — 「増え方の型」で比べる
同じ処理でも、パソコンの性能やプログラミング言語で実際の秒数は変わります。そこで、データの個数 n が増えたときに手数がどんな勢いで増えるかという「型」だけを取り出して比較します。これを計算量（オーダー）といい、O( ) で書くのでO記法（ビッグオー）と呼びます。定数倍や小さい項は無視し、いちばん効く部分だけを見ます。
代表的なオーダー（速い順）
| オーダー | 呼び方 | n が2倍になると | 代表例 |
|---|---|---|---|
| O(1) | 定数時間 | 変わらない | 配列の添字アクセス a[i] |
| O(log n) | 対数時間 | +1回だけ増える | 二分探索 |
| O(n) | 線形時間 | 2倍 | 線形探索、合計を求める |
| O(n log n) | 準線形 | 2倍より少し多い | クイックソート、マージソート |
| O(n²) | 2乗時間 | 4倍 | バブルソート（二重ループ） |
| O(2ⁿ) | 指数時間 | 2乗になる | 総当たり（全組み合わせ） |
上ほど「データが増えても平気」、下ほど「データが増えると急に遅くなる」オーダーです。
数で見る — n が増えたときの手数
「どれくらい違うのか」を具体的な数で見ると、差の大きさが実感できます。
| n | O(log n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|---|
| 10 | 約3 | 10 | 約33 | 100 |
| 100 | 約7 | 100 | 約664 | 10,000 |
| 1,000 | 約10 | 1,000 | 約9,966 | 1,000,000 |
| 1,000,000 | 約20 | 100万 | 約2,000万 | 1兆 |
100万個のデータでも、O(log n) なら約20手。一方 O(n²) は1兆手——現実的な時間で終わりません。「整列してから二分探索」が速い理由が、この数字に表れています。
🔍 差を体感するなら：探索アルゴリズム可視化で、線形探索 O(n) と二分探索 O(log n) の比較回数を並べて見られます。個数を31個にすると、線形は最大31回・二分は最大5回。ソートアルゴリズム可視化では、O(n²)のバブルソートとO(n log n)のクイック・マージソートの手数の違いをアニメと数字で確かめられます。
なぜ定数や小さい項を無視するの？
O記法は「nがとても大きいときの振る舞い」を見る道具だからです。たとえば 3n + 100 という手数でも、nが十分大きければ +100 や係数 3 より n の大きさが結果を支配します。だから O(n) とだけ書きます。同様に n² + n は O(n²)。いちばん速く伸びる項だけを残すのがO記法のルールです。
時間計算量と空間計算量
計算量には、処理時間の伸びを表す「時間計算量」と、使うメモリ量の伸びを表す「空間計算量」があります。速さとメモリはトレードオフになることが多く、たとえばマージソートは高速（O(n log n)）ですが、作業用の配列に追加メモリ（O(n)）が要ります。アルゴリズム選びは「時間 vs メモリ」の兼ね合いでもあります。
基本情報技術者試験ではこう出る
「線形探索と二分探索の計算量」「バブルソートの計算量（O(n²)）」「データ数が増えたときの処理時間の増え方」「最悪・平均計算量の違い」が定番です。押さえるべきは、速い順に O(1) ＜ O(log n) ＜ O(n) ＜ O(n log n) ＜ O(n²) ＜ O(2ⁿ) の並びと、二分探索＝O(log n)、単純な二重ループ＝O(n²) という代表例。可視化で比較回数を見ておくと、選択問題で迷いません。
よくある質問
Q. O(n log n) より速いソートはないの？
A. 「値を比較して並べる」タイプのソートは、原理的に最速でも O(n log n) です。ただし、値の範囲が限られている場合は、比較を使わない特殊なソート（バケットソート・基数ソートなど）で O(n) に近づけることもあります。
Q. O(1) は「一瞬」という意味？
A. 「データ数が増えても手数が変わらない（一定）」という意味で、必ずしも高速とは限りません。定数が大きければ遅いこともあります。あくまでnに対して増えないことを表す記号です。
Q. 実務で計算量を気にする場面は？
A. データ件数が将来大きく増える処理（ログ集計、検索、一覧表示など）です。件数が少ないうちは O(n²) でも動きますが、増えると突然重くなります。設計時に「n が大きくなったらどうなるか」を見積もるのに使います。
まとめ
計算量は、データが増えたときの手数の伸び方を型で表したもの。O(1)＜O(log n)＜O(n)＜O(n log n)＜O(n²)＜O(2ⁿ) の順を覚え、代表例（二分探索＝O(log n)、二重ループ＝O(n²)）と結びつければ、試験でも実務でも役立ちます。数字と可視化で「差の大きさ」を体で覚えておきましょう。
関連ページ: 探索アルゴリズム可視化 ／ ソートアルゴリズム可視化 ／ データ構造をやさしく図解 ／ 記事一覧