数据结构中的大O表示法

渐进分析是研究算法性能随输入规模变化而变化情况的方法。我们使用大O表示法来将运行时间的增长渐进地限制在某个常数因子的上下范围内。执行一个算法所需的时间、存储空间和其他资源量决定了它的效率。渐进表示法用于确定效率。对于不同类型的输入，一个算法的性能可能会有所不同。随着输入规模的增大，性能也会发生波动。

当输入趋向于某个特定值或极限值时，渐进表示法用于表示一个算法执行所需的时间。例如，当输入数组已经排序时，该方法所花费的时间是线性的，这是最好的情况。

然而，当输入数组是逆序时，该方法需要最长的时间（二次方级）来对项目进行排序，这是最坏的情况。当输入数组既未排序也非逆序时，它需要平均时间。渐进表示法用于表示这些时长。

大O表示法根据函数的增长率对函数进行分类：具有相同增长率的几个函数可以用相同的大O表示法来表示。使用符号O是因为函数的增长率也被称为函数的阶。一个函数的大O表示法描述通常只提供了该函数增长率的一个上界。

拥有一种渐进表示法会很方便，它的意思是“运行时间的增长最多是这么多，但它也可能增长得更慢。”我们正是为此类场合使用“大O”表示法。

大O表示法的优点

• 在使用运行时输入来分析算法效率时，渐进分析非常有用。否则，如果我们通过传递不同输入的测试用例来手动进行，性能可能会随着算法输入的变化而变化。
• 当算法在多台计算机上执行时，其性能会有所不同。因此，我们选择一个性能不会随着输入数量增加而发生太大变化的算法。因此，数学表示法可以清晰地理解一个算法运行时间的上限和下限。

示例

现在让我们更深入地看一些大O表示法的例子

O(1)

这个函数相对于其输入以 O(1) 的时间（或“常数时间”）运行。输入数组可以是 1 个项目或 1,000 个项目，但这个函数仍然只需要一步。

O(n)

这个函数以 O(n) 的时间（或“线性时间”）运行，其中 n 是数组中的项目数。如果数组有 10 个项目，我们必须打印 10 次。如果它有 1000 个项目，我们必须打印 1000 次。

O(n^2)

这里我们嵌套了两个循环。如果我们的数组有 n 个项目，外层循环运行 n 次，内层循环在外层循环的每次迭代中都运行 n 次，总共打印 n^2 次。如果数组有 10 个项目，我们必须打印 100 次。如果它有 1000 个项目，我们必须打印 1000000 次。因此，这个函数以 O(n^2) 的时间（或“二次方时间”）运行。

O(2^n)

O(2^n) 函数的一个例子是斐波那契数的递归计算。O(2^n) 表示一个算法，其增长速度随着输入数据集的每次增加而加倍。O(2^n) 函数的增长曲线是指数级的——开始时非常平缓，然后急剧上升。

因此，在本文中，我们理解了数据结构中的大O表示法是什么，以及我们如何在日常实践中使用它来理解我们日常交付成果的时间复杂度。