O(n)は、入力サイズnが十分大きいとき、処理回数などの増え方を定数倍のnで上から抑えられることを表します。一般には「線形時間」の説明で登場しますが、実行時間が必ず厳密にnに比例するという意味ではありません。
O(n)の見方：秒数より増え方に注目
例えば、n個の値をすべて足す処理で、各要素の加算を一定時間と考えるなら、処理回数はnに比例して増えます。3n＋5のような式もO(n)です。定数倍や低次の項を省き、入力が増えたときの傾向を比べます。
処理回数が上下とも定数倍のnで挟めるときはΘ(n)と表せます。Oは上界なので、O(1)の処理も数学的にはO(n)に含まれます。学習で「O(n)のアルゴリズム」と分類するときは、通常はより適切な小さいオーダーを使っています。
具体例：配列の全要素の合計
total = 0
for each x in array: // 要素数 n
total = total + x全n要素を1回ずつ読むので、各操作を一定時間とするモデルではΘ(n)です。ここでの「走査」は配列などの要素を順に調べる意味で、画像を読み取るスキャンに限定しません。
線形探索は最良と最悪を分ける
先頭から目的の値を探して見つかれば終了する線形探索では、先頭にあれば比較1回で最良Θ(1)、末尾にあるか存在しない場合は最大n回で最悪Θ(n)です。「線形探索はO(n)」という説明では、どの場合の上界かを確かめましょう。
他のオーダーと比較
| 代表的な増え方 | 例・前提 | nが10倍のときの目安 |
|---|---|---|
| O(1) | 配列の指定位置へのアクセスを一定時間とする | 一定 |
| O(log n) | 整列済み配列の二分探索の最悪時 | 対数的に増える |
| O(n) | 全要素の合計 | 線形の主要項なら約10倍 |
| O(n log n) | マージソートの比較回数など | nより速く増える |
| O(n²) | 各n回のループを二重に実行 | 二乗の主要項なら約100倍 |
実測秒数は機器・実装・キャッシュ・入力内容などにも左右されます。O記法だけから正確な秒数や、小さい入力で必ず速いアルゴリズムを決めることはできません。
ループの形だけで決めない
- ループ内に別のO(n)処理があれば、外側n回で全体O(n²)になることがある。
- 2本のn回ループを順に実行すると2n相当でO(n)。
- 二重ループでも反復範囲が定数や対数なら、必ずO(n²)とは限らない。
確認問題
一定時間の処理をn回行うループを、続けてもう一度n回行います。全体の適切な時間計算量はどれでしょうか。
- O(1)
- O(n)
- O(n²)
- O(2ⁿ)
解答・解説を見る
正解：2。n＋n＝2nなので、定数倍を省いてO(n)です。二つのループが入れ子の場合とは区別します。
noteで計算量の見分け方を練習する
O記法の意味を押さえたら、ループや代表的なアルゴリズムから計算量を判断する練習へ進みましょう。
コメント