算法导论学习笔记(二)

Posted by HK on February 1, 2019

第三章 给出几种标准方法来简化算法的渐近分析,以及在算法分析中常见的若干函数的行为。

第三章 函数的增长

渐近记号

主要使用渐近家伙来描述算法的运行时间。

标准记号与常用函数

单调性:若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的一个因子。

多项式

指数