情報科学 › アルゴリズムとデータ構造 › 探索アルゴリズム

比較モデルにおける探索の下界

定理 4.1（「探索アルゴリズム」§4）・ ✓公理まで証明済み

$n \ge 1$ とします。比較モデル（定義 2.2）で動く任意の決定的アルゴリズム $\mathcal{A}$ が、昇順にソートされた長さ $n$ の配列 $A$ とキー $x$ を入力として $\mathrm{lb}_A(x)$ を出力するならば、ある入力 $(A, x)$ に対して $\mathcal{A}$ は少なくとも $\lceil \log_2 (n+1) \rceil$ 回の比較を行います。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

前提をたどる証明が使う定理・定義

証明は Rikai の他の定理を参照していません（定義と論理だけで示されています）。

これを使っている定理証明で参照している 1 件

二分探索の最適性✓系 4.2・探索アルゴリズム

関連するノック 1 問

アルゴリズム第 28 問