复杂度函数的阶 设∫和g是定义域为自然数集N上的函数 f(n=o(g(n)) 若存在正数c和m使得对一切心有0≤fm)cg(n) f(m)=(g(m) 若存在正数c和h使得对一切n有0≤cg(m)≤八m) f(m)=0(g(m) 对所有正数c<1存在m使得对一切n≥1有0≤f(m)<cg(m) f(n)=⊙(g(m) f(n=O(g(n)A f(n)=2(g(n) O(1表示常数函数10 复杂度函数的阶 设 f 和 g 是定义域为自然数集 N 上的函数 f(n)=O(g(n)). 若存在正数 c 和 n0使得对一切 n≥n0有 0≤f(n)≤cg(n) f(n)= Ω(g(n)). 若存在正数 c 和 n0使得对一切 n≥n0有 0≤cg(n)≤ f(n) f(n)=o(g(n)). 对所有正数 c<1 存在 n0使得对一切 n≥n0有 0≤f(n)<cg(n) f(n)=Θ(g(n)) f(n)=O(g(n)) 且 f(n)=Ω(g(n)) O(1)表示常数函数