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

線形探索の比較回数

命題 2.3（「探索アルゴリズム」§2） ・ ✓公理まで証明済み

長さ nn の配列 A[0..n−1]A[0..n-1] の要素はすべて相異なるとし、キー xx を A[0],A[1],…A[0], A[1], \ldots の順に比べていく線形探索を考えます。

  1. xx が AA のどこにも現れないとき、比較回数はちょうど nn 回です。
  2. xx が AA のいずれかの位置に等確率で現れるとき、比較回数の期待値は (n+1)/2(n+1)/2 回です。

いずれの場合も計算量は Θ(n)\Theta(n) です。

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

閉包の状態

✓ 公理まで証明済み

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

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

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

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

これを使っている定理

証明で明示的に参照している定理は、まだありません。