情報科学 › アルゴリズムとデータ構造 › 探索アルゴリズム
倍々リサイズのならし計算量
空のハッシュ表（初期容量 ）から始め、負荷率が に達するたびに容量を 2 倍にして全要素を新しい表に入れ直すとします。1 回のキー挿入自体の費用と、1 個の要素の入れ直しの費用をそれぞれ定数とみなすと、 回の挿入にかかる総費用は です。すなわち 1 回の挿入あたりのならし費用は です。
閉包の状態
✓ 公理まで証明済み
証明が使う定理を 前提 としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 2 件、定義なども含めて 3 件）。
印の意味: ✓公理まで証明済み ・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は 閉包の状況。
前提をたどる 証明が使う定理・定義（直接 1 件）
▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。
動的配列の償却計算量✓定理 3.3・基本的なデータ構造
配列の基本操作の計算量✓命題 3.2・基本的なデータ構造
- 配列定義 3.1・基本的なデータ構造
これを使っている定理
証明で明示的に参照している定理は、まだありません。