算法导论-3函数增长率
目录
1. 渐进记号O、Ω、Ɵ的定义及其使用
Ɵ(big-theta)：渐近紧确界记号。
O(big-oh)：渐近上界记号
定义：设f(n)和g(n)是定义域为自然数集N上的函数。若存在正数c和n0，使得对一切n≥n0都有0≤f(n)≤cg(n)成立，则称f(n)的渐进的上界是g(n)，记作f(n)=O(g(n))。通俗的说n满足一定条件范围内，函数f(n)的阶不高于函数g(n)。
根据符号O的定义，用它评估算法的复杂度得到的只是问题规模充分大时的一个上界。这个上界的阶越低，评估越精确，越有价值。
几种常见的复杂度关系
Ω(big-omega)：渐近下界记号
定义：设f(n)和g(n)是定义域为自然数集N上的函数。若存在正数c和n0，使得对一切n≥n0都有0≤cg(n)≤f(n)成立，则称f(n)的渐进的下界是g(n)，记作f(n)=Ω(g(n))。通俗的说n满足一定条件范围内，函数f(n) 的阶不低于函数g(n)。
根据符号Ω的定义，用它评估算法的复杂度得到的只是问题规模充分大时的一个下界。这个下界的阶越高，评估越精确，越有价值。
2. 标准复杂性函数及其大小关系