【有书共读】《算法导论》第3章 - 函数的增长 读书笔记
当输入规模足够大，使得只有运行时间的增长量级有关时，我们要研究算法的渐进效率。
渐近记号
Θ记号
Θ记号渐近地给出一个函数的上界和下界。对一个给定的函数g(n)，用Θ(g(n))来表示以下函数的集合：
值得注意的是，我们通常会用这样一种方式活用等式：用“f(n) = Θ(g(n))”表达与"f(n) ∈ Θ(g(n))"相同的概念。
对于所有n≥n0，如果函数f(n)在一个常量因子内等于g(n)，我们称g(n)是f(n)的一个渐近紧确界。
Ο记号
当只有一个渐近上界时，使用Ο记号。对于给定的函数g(n)，用Ο(g(n))（读作“大Og(n)”，有时仅读作“Og(n)”）来表示以下函数的集合：
Ω记号
Ω记号提供了渐近下界。对于给定的函数g(n)，用Ω(g(n))（读作“大Ωg(n)”，有时仅读作“Ωg(n)”）来表示以下函数的集合：
根据目前所看到的这些渐近记号的定义，容易证明以下重要定理：
o记号
由O记号提供的渐近上界可能是也可能不是紧确的。界2n2 = O(n2)是渐近紧确的，但是界2n = O(n2)却不是。我们使用o记号来表示一个非渐近紧确的上界。形式化地定义o(g(n))（读作“小og(n)”）为以下集合：
例如，2n = o(n2)，但是2n2 ≠ o(n2)
ω记号
ω记号与Ω记号的关系类似于o记号与O记号的关系。我们使用ω记号来表示一个非渐近紧确的下界。定义它的一种方式是：
或者形式化地定义它：
其他
本章中介绍的其他数学概念较为简单和常用，便不在此赘述。
#笔记##读书笔记#
哔哩哔哩公司福利 596人发布
