Big(O) 的准确定义

Question

我正在做关于数据结构和算法的课程的笔记。

导师给了我们以下“O(n)时间复杂度”的定义：

O(n) - 线性时间
当算法的执行时间与输入 (n) 的大小成比例线性增长时，该算法被认为具有 O(n) 的复杂度。

下图解释了与定义相关的内容：

我真的不太喜欢这个定义，因为它只考虑了时间。
我们都知道 Big(O) 是关于时间和空间复杂性。

所以这是我想到的一个更通用的定义：

O(n)
当算法执行的操作数量与输入 (n) 的大小成比例线性增长时，算法被认为具有 O(n) 的复杂度。

这样定义与图表也会更加一致。

大家觉得怎么样？您认为最好的定义是什么？
我知道这是一个非常重要的主题，所以我希望我的笔记能够以最好的方式写出来！

Answer 1

澄清

我们都知道 Big(O) 是关于时间和空间复杂性的。

这也不完全正确。 Big-O 本身是应用于函数的通用数学构造。就其本身而言，它与编程或算法无关。如何使用该工具完全取决于您。您可以将它用于不仅仅是算法的时间和空间。

定义

Big-O（及其朋友小-O、大-omega、小-omega 和 Theta）的正确定义当然是完整的数学定义，不留任何解释空间。那是（来自维基百科）：

阅读：

f in O(g)

当且仅当存在一个常数

C > 0

，一个数字

x_0 > 0

，这样对于所有

x > x_0

都成立

|f(x)| <= C * |g(x)|

说明

简单来说，这意味着函数

f

渐近增长小于（或等于）

g

。

• 渐近地 - 我们不关心

  f

  一开始的表现，只关心它接近无穷大时
• 增长 - 我们不关心

  f

  和

  g

  的绝对值，我们只比较它们的增长。

如你所见，它只讨论函数，而不讨论代码或算法。如何弥合这一差距以应用此工具完全取决于您。在编程实践中，我们经常尝试用数学函数来表示代码的运行时间（或者空间消耗），然后应用这个工具。然而，我们还可以将其应用于更多。

注意

一些注意事项。请注意 Big-O 的局限性。如果算法不根据输入改变其执行时间，则需要一年才能执行的算法仍然可以处于

O(1)

状态。因此，仅仅因为一种算法在

O(1)

中，另一种算法在

O(n^5)

中，并不一定意味着前者更好。当应用于合理规模的问题时，可能完全是“更差”算法（就复杂性而言）是“更好”算法。