可加速函式(speedable function)一種不存在最佳算法的可計算函式.設g為一個二元遞歸函式，且關於其第二變元是嚴格遞增的，}- }}i }r}E‘為複雜性測度，f為遞歸函式。
如果
b Z (.f一中~}.i<f = }邑y a.e.x(g(x,};(x))<};<x)))).則稱f有一個(關於中的)g加速.稱函式f稱為(g)可加速的.不是可加速的函式稱為不可加速的.注意到g關於第二變元之嚴格遞增條件保證了g(x,y;y.因此，當f是g可加速的函式時，對任何一個計算f的算法M;(即f一外時)，總存在另一個更好的算法M;來計算f，而且M;的複雜性中，比之M;的複雜性中至少有一個g改進量.如當gCx}y)=Cx+1) ' y時，改進後的算法複雜性電}x)小於};(x)/Cx+1)，即ba. e. x(};(二)G}; Cx)/Cx十1)).值得指出的是，一個函式是否為可加速的，與具體的
b Z (.f一中~}.i<f = }邑y a.e.x(g(x,};(x))<};<x)))).則稱f有一個(關於中的)g加速.稱函式f稱為(g)可加速的.不是可加速的函式稱為不可加速的.注意到g關於第二變元之嚴格遞增條件保證了g(x,y;y.因此，當f是g可加速的函式時，對任何一個計算f的算法M;(即f一外時)，總存在另一個更好的算法M;來計算f，而且M;的複雜性中，比之M;的複雜性中至少有一個g改進量.如當gCx}y)=Cx+1) ' y時，改進後的算法複雜性電}x)小於};(x)/Cx+1)，即ba. e. x(};(二)G}; Cx)/Cx十1)).值得指出的是，一個函式是否為可加速的，與具體的
