渐进复杂度

渐近分析

利用渐近分析，我们可以根据输入规模了解算法的性能。我们不应该计算确切的运行时间，而应该找到运行时间和输入规模之间的关系。当输入规模增加时，我们应该关注运行时间的变化。

对于空间复杂度，我们的目标是获得一个关系或函数，描述算法完成所需在主内存中占用的空间量。

渐近行为

对于函数**f(n)**，渐近行为是指当n变大时f(n)的增长情况。不考虑小的输入值。我们的任务是找到当输入值很大时需要花费多少时间。

例如，f(n) = c * n + k 表示线性时间复杂度。f(n) = c * n² + k 表示二次时间复杂度。

算法分析可以分为三种不同的情况。这些情况如下所示：

**最佳情况** - 在这里计算运行时间的下界。它描述了算法在最佳条件下的行为。

**平均情况** - 在这种情况下，我们计算算法运行时间的上界和下界之间的区域。在这种情况下，执行的操作数量既不是最小也不是最大。

**最坏情况** - 在这种情况下，我们计算算法运行时间的上界。在这种情况下，执行的操作数量最多。

Arnab Chakraborty

更新于： 2019年8月2日

5K+ 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习