Big O 表示法

11.1 Big O 表示法定义

Big O 表示法是一种数学表示法，用来描述算法的执行时间上限或资源消耗与输入数据大小的关系。它帮助我们了解算法的扩展性及其在数据量增加时性能的变化。

Big O 表示法关注算法中最显著的部分，忽略常数和不太重要的项，帮助我们专注于算法的长期行为。

主要表示法：

O(1) — 常数复杂度：

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

O(n) — 线性复杂度：

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

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

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

O(n^2) — 平方复杂度：

• 算法的执行时间平方依赖于输入数据的大小。
• 例子：冒泡排序，插入排序。

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

• 算法的执行时间指数依赖于输入数据的大小。
• 例子：通过穷举法解决背包问题。

注意。你会在后面的讲座中了解更多关于二分查找，冒泡排序和“背包问题”的内容。

11.2 Big O 表示法的解释

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

忽略常数和不那么重要的项： Big O 描述函数的增长速率，忽略常数和不太重要的项。例如，O(2n) 和 O(3n) 都被解释为 O(n)。

算法比较： Big O 允许我们按渐近效率比较算法。例如，一个 O(n log n) 的算法比 O(n^2) 的算法更高效，特别是对于非常大的数据量。

最坏情况分析： Big 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)。

11.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) 的算法将对 10 000 个元素大约执行 100 000 000 次操作。
• 具有 O(n log n) 的算法将为 10 000 个元素执行大约 40 000 次操作。

例子 2:

考虑一个执行时间为 O(2^n) 的算法。如果我们将输入数据大小从 10 个增加到 20 个元素，操作数量会呈指数增长。

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

这显示了对于较大的 n，指数复杂度是如何快速变得不切实际的。

1

Опрос

数据结构,  52 уровень,  4 лекция

недоступен

数据结构

数据结构

Открыть