計算量とは？O(n)・O(log n)・O(n²)を、作業回数で理解する

計算量は、入力が増えたときに必要な時間や記憶領域がどう増えるかを考える尺度です。実行秒数との違いと、よく見るO記法を具体的な作業で整理します。

定義の参考：NIST: big-O notation。以下の身近な例は説明用に作成したものです。

「1秒で終わる」だけでは比較しにくい

100件の名簿を調べるプログラムが1秒で動いたとしても、100万件で実用的かはまだ分かりません。端末の性能や保存場所でも秒数は変わります。計算量では、件数をnとして、比較や計算の回数がnに対してどう増えるかに注目します。

時間計算量は処理の手間、空間計算量は必要な記憶領域の増え方を扱います。速くするために検索用の表を保存すれば、時間は減ってもメモリが増える場合があります。どちらも「少なければ常に最善」とは限らず、用途の制約と一緒に見ます。

代表的な増え方を、同じ件数で比べる

名簿を先頭から全部確認する処理は、件数に比例するO(n)の例です。並べ替え済みの配列で候補を半分ずつ減らす二分探索はO(log n)。全員の組み合わせを調べるなら、組数はn(n−1)/2なのでO(n²)になります。

O記法は、ストップウォッチの予言ではない

O記法は、十分に大きな入力に対する増加の上限を、定数倍を許して表します。例えば3n＋20はO(n)です。20回の準備や1件あたり3回という違いを省き、入力の増加による大きな傾向を見ています。厳密には緩い上限も書けるため、O(n)と書ける処理はO(n²)とも書けます。通常は説明に役立つ小さい上限を示します。

O記法自体に「最悪の場合」という意味があるわけではありません。最悪時・平均時・最良時のどれを評価した式なのかは別の指定です。先頭に答えがある探索と、最後まで見つからない探索を混ぜると比較を誤ります。

入力が小さいと、定数の差も効く

O(n)の方法に大きな準備処理が必要なら、小さい入力ではO(n²)の単純な方法が速いこともあります。ディスクやネットワークの待ち時間、メモリ配置、使う言語でも実測値は変わります。計算量で候補を絞り、対象のデータと端末で測る、という順番が現実的です。

また、nが「人数」なのか「数字を表す桁数」なのかでも意味が変わります。計算量を見るときは、①入力の大きさ、②数える処理、③最悪か平均か、④前処理を含むかを確認しましょう。手順そのものについてはアルゴリズムを先に読むとつながります。

関連する言葉から理解を広げる

AI・コンピュータの用語8選では、関連する概念を具体例と一緒に比較できます。