定义4.7设(m)和/(为图灵机M和M的 计算复杂性,若f(=O(m),则称算法M 不比算法M有效;若/(m)=(m),则称算 法M和M是等效的:若存在正整数d, ∫n(m)=On),则称M为多项式时间算法,按 密码学中的传统观念,认为多项式时间 算法为有效算法;若f)=2),则称M 为亚指数时间算法;若/m)=2或0), 则称M为指数时间算法。亚指数和指数 时间算法也被称为超多项式时间算法, 为不是有效算法• 定义4.7 设 和 为图灵机M和 的 计算复杂性，若 ，则称算法 不比算法M有效；若 ，则称算 法M和 是等效的；若存在正整数d， ，则称M为多项式时间算法，按 密码学中的传统观念，认为多项式时间 算法为有效算法；若 ，则称M 为亚指数时间算法；若 ， 则称M为指数时间算法。亚指数和指数 时间算法也被称为超多项式时间算法， 被认为不是有效算法。 f (n) M f ' (n) M ' M f (n) ( f ' (n)) M M =  ' M f (n) ( f ' (n)) M M =  ' M ( ) ( ) d f M n =  n ( ) (2 ) logn f M n =  ( ) (2 ) 10 ) n n f M n =  或（