増大度の階層

定理 4.2（「計算量と O 記法」§4）・ ✓公理まで証明済み

$a > 0$ , $\varepsilon > 0$ , $k \ge 0$ , $c > 1$ を任意の実数とする。このとき

(\log_2 n)^a \in o(n^{\varepsilon}), \qquad n^k \in o(c^{\,n}), \qquad c^{\,n} \in o(n!)

が成り立つ。とくに $\varepsilon = 1$ 、 $a = 1$ 、 $c = 2$ と取れば、 $\log_2 n$ 、 $n$ 、 $2^n$ 、 $n!$ はこの順に真に大きなオーダーである。

閉包の状態

✓ 公理まで証明済み

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

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

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

指数は多項式に勝つ✓補題 4.1・計算量と O 記法
極限による判定法✓命題 3.3・計算量と O 記法
- O 記法・Ω 記法・Θ 記法定義 3.1・計算量と O 記法
- o 記法・ω 記法定義 3.2・計算量と O 記法

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