大O表示法：基本概念

2.1 大O表示法的定义

大O表示法是一个数学表示法，用于描述算法的时间复杂度或资源消耗的上限，依据输入数据的大小。它帮助我们了解当数据量增加时，算法如何扩展和性能如何变化。

大O表示法关注算法最重要的方面，忽略常数和不太重要的成员项，使得我们可以专注于算法的长期行为。

基本表示法：

O(1) — 常数复杂度：

• 算法的执行时间不随输入数据大小而变化。
• 例子：通过索引访问数组元素。

O(n) — 线性复杂度：

• 算法的执行时间线性地依赖于输入数据的大小。
• 例子：简单遍历数组中的所有元素。

O(log n) — 对数复杂度：

• 算法的执行时间随着输入数据大小以对数方式增长。
• 例子：在排序数组中进行二分查找。

O(n^2) — 二次复杂度：

• 算法的执行时间与输入数据大小的平方成正比。
• 例子：冒泡排序，插入排序。

O(2^n) — 指数复杂度：

• 算法的执行时间与输入数据大小的指数成正比。
• 例子：使用全部组合解决背包问题。

2.2 大O表示法的解释

如何解释和使用大O表示法？

忽略常数和不太重要的项：

大O描述的是函数的增长趋势，忽略常数和不太重要的项。比如，O(2n) 和 O(3n) 解释为 O(n)。

比较算法：

大O用于比较算法的渐进效率。例如，O(n log n) 的算法比 O(n^2) 的算法对大数据量更有效率。

分析最坏情况：

大O通常用于分析算法在最坏情况下的时间复杂度，以评估其最大复杂度。

忽略常数。

忽略常数和不太重要的项

例子 1：

考虑两个函数：

• f(n) = 3n + 2
• g(n) = 5n + 1

两个函数都具有线性复杂度，因为每个函数的主要成员是 n。因此，尽管系数和附加项不同，它们都解释为 O(n)。

例子 2：

考虑两个函数：

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

两个函数都具有二次复杂度，因为主要成员是 n^2。尽管其他成员和系数不同，它们都解释为 O(n^2)。

2.3. 比较算法

1. 在非常大的数据量上比较算法

例子 1：

• 算法 A 的时间复杂度为 O(n^2)。
• 算法 B 的时间复杂度为 O(n log n)。

对于较小的 n，由于较小的常数，算法 A 可能更快，但对较大的 n，算法 B 将显著更快，因为其增长是对数而非二次的。

例子 2：

• 算法 X 的时间复杂度为 O(n)。
• 算法 Y 的时间复杂度为 O(1)。

无论 n 的大小如何，算法 Y 都将总是更快，因为 O(1) 意味着算法的执行时间不依赖于输入数据的大小。

2. 最坏情况分析

例子 1：

冒泡排序在最坏情况下的时间复杂度为 O(n^2)，当数组按反序排列时。这意味着对于数组中的每个元素，可能需要与其他所有元素进行比较和交换。

例子 2：

二分查找在最坏情况下的时间复杂度为 O(log n)。这意味着即使在最坏的情况下，找到元素所需的步骤数量与数组的大小呈对数关系，非常有效。

3. 对性能和可扩展性的影响

例子 1：

如果我们有两个处理数据的算法，一个的时间复杂度是 O(n^2)，另一个是 O(n log n)，当我们将数据规模从1000个元素增加到10,000个时，性能差异将十分明显。

• O(n^2) 的算法将执行大约 100,000,000 次操作以处理10,000个元素。
• O(n log n) 的算法将执行大约 40,000 次操作以处理10,000个元素。

例子 2：

考虑一个时间复杂度为 O(2^n) 的算法。当我们将输入数据大小从10增加到20时，操作数量将成指数增长。

• 对于 n = 10: 2^10 = 1024 次操作。
• 对于 n = 20: 2^20 = 1,048,576 次操作。

这展示了当 n 较大时，指数复杂度如何迅速变得不切实际。