概念・定理図鑑 · 入門

O記法:大きな入力での増え方の上限

定数倍を含む上界として定義し、厳密な増加率、最悪計算量、実行時間との違いを具体例で確認します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. ある地点から先の上界
  2. 3n+4を評価する
  3. 最悪・平均・償却は評価対象の選び方
  4. 秒数や優劣を決める表ではない
  5. 二つの入力次元を残して評価する
  6. この記事をロゲイアに質問する理解を確かめる

ある地点から先の上界

O記法は、関数の増え方を定数倍まで許して上から抑える表記です。十分大きなnに対してT(n)≦c・f(n)となる正の定数cと開始点n0を選べれば、T(n)はO(f(n))と書けます。すべての小さい入力で式がそのまま成り立つ必要はありません。この定義は入力規模が増えたときの議論をしやすくしますが、定数を無視してよい場面と、実際に測定すべき場面を区別する必要があります。

3n+4を評価する

T(n)=3n+4なら、n≧1で3n+4≦7nなのでO(n)です。同時にO(n²)などの緩い上界でもあります。Oは「ちょうど同じ増え方」を要求しないためです。上下から同じ増え方で挟むことを表したいならΘ記法などを区別します。「O(n²)だから必ず二次関数と同じだけ遅くなる」と読むのではなく、その記述が上界なのか、より厳密な評価も得られているのかを確認します。

最悪・平均・償却は評価対象の選び方

O記法そのものが「最悪の場合」を意味するわけではありません。最悪時の処理回数を関数T(n)にすれば最悪計算量の上界になり、期待値を関数にすれば期待計算量の上界になります。償却計算量も、操作列をまとめて評価する別の考え方です。例えばハッシュ表の期待O(1)という説明を、どんな入力でも一回の操作が必ず定数時間と読み替えてはいけません。対象の入力モデルと仮定を一緒に読みます。

秒数や優劣を決める表ではない

二つの実装がO(n)でも、定数やメモリアクセス、並列性などにより処理時間は異なります。また、小さな入力では定数の小さいO(n²)の実装が、大きな準備費用を持つO(n log n)の実装より速い場合もあります。漸近解析は測定の代わりではなく、入力が増えたときの見通しを与えるものです。比較では入力サイズの定義、支配する処理、実行条件を明示し、必要に応じて実測と組み合わせて選択します。

二つの入力次元を残して評価する

n行m列の表をすべて一度ずつ調べる処理は、各要素の検査が定数費用ならO(nm)と評価できます。mが常に固定値8なら、nだけについてO(n)と書けます。一方、mもnと同じように増え、m=nという条件ならO(n²)になります。「二重ループだから常にO(n²)」と決めず、それぞれの反復回数と入力サイズの定義を確認します。また、各反復で長さkの文字列を比較するなら、その比較を定数費用と仮定できるかも検討が必要です。支配項を選ぶ前に、何を入力とし、どの操作を一回として数えるモデルかを明確にすると、誤った単純化を避けられます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 5

AI基盤へ進む · STEP 2

学習コースから次を選ぶ