アルゴリズムとプログラミングアルゴリズムとデータ構造

O 記法（ビッグオー）に関する記述として、最も適切なものはどれか。

ア.アルゴリズムが必ず要する最良の実行時間を表す。

イ.アルゴリズムの実行時間の上界（最悪に近い増え方）を漸近的に表す。正解

ウ.アルゴリズムが消費する記憶領域の正確な値を表す。

エ.アルゴリズムの正しさを形式的に証明する記法である。

解説

O 記法は「入力が増えたとき、計算量がどれくらいまでで収まるか」の上限を雑に表す道具。実時間の正確値ではなく「天井のオーダー」です。

なぜイが正解か

イが正解。O(f(n)) は「ある定数 c と n₀ が存在し、n ≥ n₀ で T(n) ≤ c·f(n)」という意味で、計算量の漸近的上界を表します。最悪計算量を雑に押さえる用途で使われ、定数や低次の項は無視するのが流儀です。

なぜアは間違いか

Ω（オメガ）記法は漸近的な下界を表す記法で、最良ケースの分析でよく用いられますが、O記法の「上界」とは対の概念です。O記法を問われているのにΩを答えるのは、天井の高さを聞かれて床の位置を答えるようなものです。

なぜウは間違いか

正確な値ではなくあくまで「オーダー」を表すのが O 記法の役割。実測値や正確なメモリ量を伝えたいときは別の指標が必要です。

なぜエは間違いか

アルゴリズムの正しさを示すのはホーア論理や数学的帰納法などの証明手法。O 記法はあくまで効率の議論用で、正しさ証明とは関係ありません。

出典: AI生成問題（学習用）

← 前の問題

次の再帰関数 f(n) を f(5) で呼び出したときの戻り値はどれか。 f(n): if n <= 1 then return 1 else return n * f(n - 1)

次の問題 →

重み付きグラフにおいて、ある始点から各頂点への最短経路を求めるアルゴリズムとして適切なものはどれか。ただし、辺の重みはすべて非負とする。