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)，并不一定意味着前者更好。当应用于合理规模的问题时，最差的算法（就复杂性而言）可能是更好的算法。