渐近分析

由于我们有许多不同的算法可供选择,当我们想要对数组进行排序时,我们需要知道哪一个会完成它的工作。所以我们需要一些测量算法速度和可靠性的方法。这就是渐近分析的用武之地。渐近分析是随着输入大小(n)的增长而描述算法效率的过程。在计算机科学中,渐近线通常以称为 Big O Notation 的通用格式表示。

  • 线性时间 O(n) :当为了使函数达到目标而必须对数组中的每个项进行求值时,这意味着随着元素数量的增加,函数变得不那么有效。这样的函数据说以线性时间运行,因为它的速度取决于其输入大小。
  • 多项式时间 O(n2) :如果函数的复杂度指数增长(意味着对于函数的数组复杂度的 n 个元素是 n 平方),该函数在多项式时间内运算。这些通常是嵌套循环的函数。两个嵌套循环导致 O(n2) 复杂度,三个嵌套循环导致 O(n3) 复杂性,依此类推……
  • 对数时间 O(log n): 当输入(n)的大小增加时,对数时间函数的复杂性最小化。这些是每个程序员努力的功能类型。