定义45称一个图灵机M可解一个语言 L的成员识别问题,若对任一输入数 据x∈0},M在有限时刻K(x)停机,且M 的输出s 若x∈L。否则 图灵机的计算复杂性定义为 fM(n)=max[k(x) Xx=n 定义46设f(n)和g(n)为两个正整数函数, 若存在正整数和常数c使当时≥n 有(m)scgm,则记作f(m)=Og(m); l)=O(g(m),g(m)=O(/(m),则记作 f(n)=⊙(g(m)• 定义 4.5 称一个图灵机 M可解一个语言 L 的成员识别问题,若对任一输入数 据 ，M在有限时刻 停机，且M 的输出 ，若 。否则 。 图灵机的计算复杂性定义为 • 定义 4.6 设f(n)和g(n)为两个正整数函数， 若存在正整数 和常数c使当 时 有 ，则记作 ； 若 ， ，则记作   * x  0,1 K(x) t K( x) (i K( x) ) = 1 x L t K( x) (i K( x) ) = 0 ( ) max ( ) ; f n K x x x n M = = 0 n n  n0 f (n)  cg(n) f (n) = (g(n)) f (n) = (g(n)) g(n) = ( f (n)) f (n) =Θ（g(n))