【算法导论】函数的增长

2.1 渐进记号

2.1.1 θ 记号

θ()用来描述一个区间（给出了上界和下界），如下图，即0<=c_1g(n)<=f(n)<=c_2g(n).

其中常数c_1和c_2均大于0且都需要存在当n足够大时上式能够满足，则满足f(n) = θ (g(n))。

2.1.2 Ο 记号

O记号只给出了渐近上界。也就是说O()的值在 θ() 之中，我们一般用O描述算法的最坏情况。

也就是说，比如你说插入排序的时间复杂度是O(n^2)是不合适的，因为确实存在某一序列使得插入排序的时间复杂度达到 θ(n)，因此我们只能说插入排序在最坏的情况下的时间复杂度为 O(n^2) 。

也就是判断依据是 f(n)<=c_2g(n). 其中c_2也是一个大于0的常数。

2.1.3 Ω 记号

相对O的渐近上界， Ω 则给出了渐近下界。

也就是对于插入排序，我们可以说O(n^2)，也可以说 Ω (n)。

判别依据是 0<=c_1g(n)<=f(n) 。其中c_1是一个大于0的常数。

练习3.1-1

练习3.1-2

练习3.1-4

练习3.3