渐进记法

目前分析算法最好的方法是 渐进分析(asymptotic analysis),我们平常所说的的时间复杂度是指 渐进时间复杂度,空间复杂度是指 渐进空间复杂度

我们分析算法的时候一般有三种情况: 

1.最坏情况(通常可行) 

2.平均情况(有些时候可行) 

3.最好情况(基本不可行) 大多数时候,我们用最坏的情况来分析算法,这样我们就能够得到算法运行时间的上限,这也是多数情况下我们需要的。

分析算法时,我们需要关心2中情况

1.随着输入的增加这个算法需要多少时间

2.增长的速度是多少,也可以叫运行时间的增长率

为了简单可控,我们一般提取一个函数重要的部分而剔除次要部分

假设有一个算法,输入长度为 n,需要 6n² + 100n + 300 条cpu指令,随着 n 的增加,6n² 远比 100n + 300 项大,而 6n² 与 n² 也差的不多,所以我们可以说该算法运行时间随着 n² 增长。


Big-θ (Big-Theta) notation

Θ(n) - 随着 n 变大,运行时间最少 k1 * n,最多 k2 * n,k1 和 k2 是某些常量。

这里的 n 可以为任意函数f(n),比如 n²,nlog₂n,随着 n 变大,运行时间在 k1 * f(n) 和 k2 * f(n) 之间

在实际应用上,会去掉一些常数因子和低阶项(low-order term),比如 6n² + 100n + 300,运行时间为 Θ(n²)

Big-θ 记法代表运行时间的渐进严格边界(asymptotically tight bound),因为我们把运行时间固定在了上界(upper bound)和下界(low bound)之间

下面是我们在分析算法中经常遇到从低到高

需要注意,aⁿ (a>1),增长速度比 nᵇ(b常数) 快


Big-O notation

Big-θ 记法代表在上界和下界之间运行时间的增长情况,但是有些时候我们只关心上界

比如,二分超找最坏情况为 Θ( log₂n),最好的情况为 Θ(1),所以我们用 Big-θ 记法就不好使,此时 Big-O 刚好适用

假设运行时间为 O(f(n),那么当 n 够大,运行时间最大为 k * f(n)

Big-O 记法代表渐进上界(asymptotic upper bounds),所以二分查找最确切的说法是:二分查找运行时间为或者时间复杂度为O( log₂n)

也可以说,因为二分超找最坏情况为 Θ( log₂n),所以记为 O( log₂n)


Big-Ω (Big-Omega) notation

有些时候我们想说一个算法至少需要多少时间,我们就可以用这个记法

假设运行时间为 Ω(f(n),那么当 n 够大,运行时间至少为 k * f(n)

Big-Ω记法代表 渐进下界(asymptotic lower bounds),我们可以说 二分查找最坏的情况下运行时间为 Ω( log₂n)


一般情况下我们都是采用 Big-O 记法,时间复杂度最坏情况一般才是我们想要的。

参考:

Asymptotic notation

上一篇: 排列组合
下一篇: 时间复杂度计算
作者邮箱: 203328517@qq.com