Big-O Notation 中的 O 是什么意思？
What does the O in Big-O Notation mean?
在分析算法的复杂性的背景下，我正在努力思考 Landau-Notation 的含义。
O 在大 O 表示法中的正式含义是什么？
所以我的理解是 O(g(x)) 给出了一个 set 函数，其增长速度或比 g(x) 慢，这意味着，例如在 O(n^2) 的情况下：
例如，t(x) 可能是 x + 3 或 x^2 + 5。我的理解正确吗？
另外，下面的记法正确吗？
我看到一位导师写下了以下内容。这是什么意思？如果 O-Notation returns 一组，你怎么能使用 less or equal?
我也可以这样写吗？
So the way I understand it is that O(g(x)) gives a set of functions which grow as rapidly or slower as g(x).
这个Big-Oh符号的解释是正确的。
f(n) = n^2 + 5n - 2, f(n) is an element of O(n^2)
是的，我们可以这么说。 O(n^2) 用简单的英语表示“所有增长速度等于或慢于 n^2 的函数的集合”。因此，f(n) 满足该要求。
O(n) is a subset of O(n^2), O(n^2) is a subset of O(2^n)
这个符号是正确的，它来自定义。 O(n) 中的任何函数也都在 O(n^2) 中，因为它的增长速度比 n^2 慢。 2^n 是指数时间复杂度，而 n^2 是多项式。当 n 趋于无穷大时，您可以取 n^2 / 2^n 的极限，并证明 O(n^2) 是 O(2^n) 的子集，因为 2^n 变大了.
O(n) <= O(n^2) <= O(2^n)
这个符号很棘手。正如 here 所解释的那样，对于集合，我们没有“小于或等于”。我认为 tutor 的意思是属于集合 O(n) 的函数的时间复杂度小于（或等于）属于集合 O(n^2) 的函数的时间复杂度。反正这个记号看起来不太眼熟，教科书上最好不要出现这种含糊不清的地方。
O(g(x)) gives a set of functions which grow as rapidly or slower as g(x)
这在技术上是正确的，但有点不精确。更好的描述包含附录
O(g(x)) gives the set of functions which are asymptotically bounded above by g(x), up to constant factors.
这看起来像是吹毛求疵，但从不精确的定义中得出的一个推论是错误的。
你的第一个等式的 'fixed version'，如果你使变量匹配并且有一个极限符号，似乎是：
这是不正确的：比率只需要小于或等于某个固定常数c > 0。
这是正确的版本：
其中 c 是一些固定的正实数，不依赖于 n。
例如，f(x) = 3 (n^2) 在 O(n^2) 中：适用于此 f 的一个常量 c 是 c = 4。请注意，要求不是 'for all c > 0'，而是 'for at least one constant c > 0'
你的其他评论都是准确的。该表达式中的 <= 符号是一种不寻常的用法，但如果 <= 表示集合包含，则为真。我不会担心那个表达的意思。
还有其他更微妙的原因可以谈论 'boundedness' 而不是增长率。例如，考虑 cosine 函数。 |cos(x)| 在 O(1) 中，但它的导数从负一波动到正一，即使 x 增加到无穷大。
如果你把 'growth rate' 当作导数之类的东西，像这样的例子就很难说了，但是说 |cos(x)| 受 2 的限制就很清楚了。
一个更好的例子，考虑 logistic curve。逻辑函数是 O(1)，但是，它的导数和增长率（在正数上）是正的。它严格 increasing/always 增长，而 1 的增长率为 0。这似乎与第一个定义冲突，没有对 'grow' 的含义进行大量额外的澄清。
O(1)中的一个不断增长的函数（图片来自维基百科link）：
在分析算法的复杂性的背景下，我正在努力思考 Landau-Notation 的含义。
O 在大 O 表示法中的正式含义是什么？
所以我的理解是 O(g(x)) 给出了一个 set 函数，其增长速度或比 g(x) 慢，这意味着，例如在 O(n^2) 的情况下：
另外，下面的记法正确吗？
我看到一位导师写下了以下内容。这是什么意思？如果 O-Notation returns 一组，你怎么能使用 less or equal?
我也可以这样写吗？
So the way I understand it is that O(g(x)) gives a set of functions which grow as rapidly or slower as g(x).
这个Big-Oh符号的解释是正确的。
f(n) = n^2 + 5n - 2, f(n) is an element of O(n^2)
是的，我们可以这么说。 O(n^2) 用简单的英语表示“所有增长速度等于或慢于 n^2 的函数的集合”。因此，f(n) 满足该要求。
O(n) is a subset of O(n^2), O(n^2) is a subset of O(2^n)
这个符号是正确的，它来自定义。 O(n) 中的任何函数也都在 O(n^2) 中，因为它的增长速度比 n^2 慢。 2^n 是指数时间复杂度，而 n^2 是多项式。当 n 趋于无穷大时，您可以取 n^2 / 2^n 的极限，并证明 O(n^2) 是 O(2^n) 的子集，因为 2^n 变大了.
O(n) <= O(n^2) <= O(2^n)
这个符号很棘手。正如 here 所解释的那样，对于集合，我们没有“小于或等于”。我认为 tutor 的意思是属于集合 O(n) 的函数的时间复杂度小于（或等于）属于集合 O(n^2) 的函数的时间复杂度。反正这个记号看起来不太眼熟，教科书上最好不要出现这种含糊不清的地方。
O(g(x))gives a set of functions which grow as rapidly or slower asg(x)
这在技术上是正确的，但有点不精确。更好的描述包含附录
O(g(x))gives the set of functions which are asymptotically bounded above byg(x), up to constant factors.
这看起来像是吹毛求疵，但从不精确的定义中得出的一个推论是错误的。
你的第一个等式的 'fixed version'，如果你使变量匹配并且有一个极限符号，似乎是：
这是不正确的：比率只需要小于或等于某个固定常数c > 0。
这是正确的版本：
其中 c 是一些固定的正实数，不依赖于 n。
例如，f(x) = 3 (n^2) 在 O(n^2) 中：适用于此 f 的一个常量 c 是 c = 4。请注意，要求不是 'for all c > 0'，而是 'for at least one constant c > 0'
你的其他评论都是准确的。该表达式中的 <= 符号是一种不寻常的用法，但如果 <= 表示集合包含，则为真。我不会担心那个表达的意思。
还有其他更微妙的原因可以谈论 'boundedness' 而不是增长率。例如，考虑 cosine 函数。 |cos(x)| 在 O(1) 中，但它的导数从负一波动到正一，即使 x 增加到无穷大。
如果你把 'growth rate' 当作导数之类的东西，像这样的例子就很难说了，但是说 |cos(x)| 受 2 的限制就很清楚了。
一个更好的例子，考虑 logistic curve。逻辑函数是 O(1)，但是，它的导数和增长率（在正数上）是正的。它严格 increasing/always 增长，而 1 的增长率为 0。这似乎与第一个定义冲突，没有对 'grow' 的含义进行大量额外的澄清。
O(1)中的一个不断增长的函数（图片来自维基百科link）：