情報科学 › アルゴリズムとデータ構造 › 計算量と O 記法

多項式時間アルゴリズム

定義 7.1（「計算量と O 記法」§7）

アルゴリズム $A$ が多項式時間であるとは、ある定数 $k$ が存在して $T_A(n) = O(n^{k})$ が成り立つことをいう。

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

閉包の状態

定義

定義は閉包の起点です（証明を要しません）。

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

これを使っている定理

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