Speedup theorem

ウィキペディア

加速定理

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

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

例

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