「計算の複雑さ」の版間の差分
ナビゲーションに移動
検索に移動
細 ("計算の複雑さ" を保護しました。 [edit=sysop:move=sysop]) |
|||
| 2行目: | 2行目: | ||
「計算の複雑さ」とは, その計算が必要とする計算資源の量を, 入力の長さに対する関数としてとらえるものである. 計算のモデルとしては, チューリング機械やRAMのモデルが使われ, 資源としては計算時間と計算に必要な領域が評価される. 一般には入力によって計算に必要な資源は変化するので, 入力の長さに関して最悪の場合を考える. 微妙な議論をしている場合以外は, 関数の多項式倍程度の差は無視する場合が多い. | 「計算の複雑さ」とは, その計算が必要とする計算資源の量を, 入力の長さに対する関数としてとらえるものである. 計算のモデルとしては, チューリング機械やRAMのモデルが使われ, 資源としては計算時間と計算に必要な領域が評価される. 一般には入力によって計算に必要な資源は変化するので, 入力の長さに関して最悪の場合を考える. 微妙な議論をしている場合以外は, 関数の多項式倍程度の差は無視する場合が多い. | ||
| + | |||
| + | 詳しくは[[《計算の複雑さ》|基礎編：計算の複雑さ]]を参照. | ||
2007年8月8日 (水) 20:41時点における版
【けいさんのふくざつさ (computational complexity)】
「計算の複雑さ」とは, その計算が必要とする計算資源の量を, 入力の長さに対する関数としてとらえるものである. 計算のモデルとしては, チューリング機械やRAMのモデルが使われ, 資源としては計算時間と計算に必要な領域が評価される. 一般には入力によって計算に必要な資源は変化するので, 入力の長さに関して最悪の場合を考える. 微妙な議論をしている場合以外は, 関数の多項式倍程度の差は無視する場合が多い.
詳しくは基礎編：計算の複雑さを参照.