第三章 给出几种标准方法来简化算法的渐近分析,以及在算法分析中常见的若干函数的行为。
第三章 函数的增长
渐近记号
主要使用渐近家伙来描述算法的运行时间。
标准记号与常用函数
单调性:若m≤n蕴涵f(m)≤f(n),则函数f(n)是单调递增的。若m< n蕴涵f(m)< f(n),则函数f(n)是严格单调递减的。
向下取整与向上取整(p31)
模运算:对任意整数a和任意正整数n,a modn的值就是商a/n的余数,结果有0≤a modn< n。
若(a modn) = (b modn),则记a≡b (modn),并称模n时a等价于b。即a与b除以n时具有相同的余数,则a≡b(modn),等价地,a≡b(modn)当且仅当n是b-a的一个因子。