加速定理

ウィキペディア

加速定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/04 01:50 UTC 版)

計算複雑性理論における加速定理（かそくていり、英: speedup theorem）は、ある問題を解く算法に対し、同じ問題をより早く解く算法（また一般に、使用する資源がより少ない算法）の存在を示す定理である。

例

例として回文（palindrome）を認識する1-テープチューリング機械を考える。次のアルゴリズムは $O(n^{2})$ この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

ウィキペディア小見出し辞書

加速定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/05/01 09:18 UTC 版)

「ブラムの加速定理」の記事における「加速定理」の解説

複雑性測度 と2変数全域再帰的関数 を所与とする。このとき全域再帰的関数 （これはブール値関数にできる）が存在して、 の任意の指標 に対して、 の指標 が存在して、ほとんど全ての に対して次が成り立つ： は加速関数と呼ばれる。 これを必要なだけ急増加な関数とすれば、 プログラム を与える毎にそれよりも必要なだけ高速なプログラム が得られる。例えば とすれば の複雑性は である。