用于理解算法在输入长度越来越大时的行为。
渐近上界(大 O 标记)
设 f,g:N→R+,称 f(n)=O(g(n)),如果存在正整数 c,n0 使得对于每个整数 n≥n0 都有 f(n)≤cg(n)。g(n) 为 f(n) 的渐近上界。
若 g(n)=nc(c>0),则称它为多项式上界;若 g(n)=2(nδ)(δ>0),则称它为指数上界。
渐近小于(小 o 标记)
设 f,g:N→R+,称 f(n)=o(g(n)),如果对任意正实数 c 都存在正整数 n0 使得对于每个整数 n≥n0 都有 f(n)<cg(n)。也即
n→∞limg(n)f(n)=0
相关内容
参考文献