帮助使用大 O 表示法
我在尝试理解大 O 表示法的概念时遇到了一些问题。因此，根据定义，大 O 如下：如果 T(n) <= G(n) * C，则 T(n) ∈ O(G(n)) 。
由于常数“C”可以是任何整数> 0，下面这个例子不也是正确的吗？
示例：
n log n ∈ O(log n)
n log n <= log n * c
其中 C 等于 n 的值。
我知道答案是 n log n ∉ O(log n) ，但我不明白为什么 C 可以是任何常数。
预先感谢您的帮助：D
I've been having some problems trying to grasp the concept of big O notation. So, by definition big O is as follows, T(n) ∈ O(G(n)) if T(n) <= G(n) * C.
Since the the constant "C" can be any integer > 0, wouldn't this following example be true as well?
Example:
n log n ∈ O(log n)
n log n <= log n * c
Where C is equal to the value of n.
I know that the answer is that n log n ∉ O(log n) but I don't understand how since C can be any constant.
Thanks in advance for your help :D
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
c 就是一个常数。这意味着您不能说“让 c 成为 n 的值”，因为您必须先选择一些 c，然后允许比较对所有 n 成立。
换句话说，为了使某个 T(n) 达到 O(G(n))，必须存在不常数 c 使得 G(n)*c 大于 T(n)对于所有的n.
因此 n log n 不是 O(log n)，因为无论您选择什么常数，n > 。 c 将使 n log n 大于 c log n。
c is just that, a constant. This means that you can't say "let c be the value of n", because you must choose some c first and then allow the comparison to hold for all n.
In other words, in order for some T(n) to be O(G(n)), there must exist no constant c such that G(n)*c is greater than T(n) for all n.
Thus n log n is not O(log n) because, no matter what constant you choose, n > c will cause n log n to be greater than c log n.
让我重复一下你的话。
这意味着c不能依赖于n。
Let me repeat your words.
This means that c can not depend on n.
这个想法是，不等式对于任何 n 和固定 c 都成立。所以虽然你可能会发现某个 c 使得 n log n < c log n，（即任意c>n），你可以很容易地找到它不成立的其他n'（即n'>c）。
the idea is that the inequality holds for any n and a fixed c. so while you might find a certain c such that n log n < c log n, (namely any c>n), you can easily find other n' for which it doesn't hold (namely n'>c).
首先，如果 n=C 则 C 不是常数。在大多数现实世界的算法中，C 很小，因此大 O 部分通常在 n 的典型值中占主导地位。
但大 O 复杂性与大 n 算法的效率有关，尤其是当 n 接近无穷大时。换句话说，它告诉您算法的可扩展性：给定算法处理非常大或双倍工作负载的能力如何。
如果您知道 n总是，那么大 O 复杂度并不那么重要，您应该关注算法所需的挂钟时间。另外，如果您在具有相同大 O 复杂度（例如 O(n log n)）的两种算法之间进行选择，那么通常一种算法比另一种更好（例如随机枢轴快速排序通常优于二元堆排序）。
First of all, if n=C then C is not a constant. And in most real-world algorithms, C is small so the big-O part usually dominates for typical values of n.
But big-O complexity is concerned with the efficiency of an algorithm for large n, especially as n approaches infinity. In other words it tells you the scalability of an algorithm: how well a given algorithm handles a very large or doubled workload.
If you know that n is always small then the big-O complexity is not that important, rather you should focus on the wall-clock time required by the algorithm. Also, if you are choosing between two algorithms that have the same big-O complexity (e.g. O(n log n)), quite often one is better than the other (e.g. random-pivot quicksort generally outperforms a binary heap sort).
在定义中，您应该仅通过 T 和 G 本身来确定 C。这就是常数 C 的含义。所以C不应该依赖于他们的输入。所以可以不考虑C=n
In the definition you should determine C just by the T and G themselves. This is what a constant C means. So C should not depend on the input of them. So you can not consider C = n
在表达式 n log n 中，您不能像您所做的那样将外部 n 与 C 进行比较。这就像采用代数表达式 x(x+1) 并用常数替换 x 之一。
在 n log n 中，n 是一个变量。在大O表达式中，C是一个常数。
in the expression n log n, you can't compare the outside n to C, like you are doing. That would be like taking the algrebraic expression x(x+1) and replacing one of the x's with a constant.
In n log n, n is a variable. In the big O expresion, C is a constant.
n的值取决于输入集，C的值是固定的。
所以，是的，如果 n = 16 且 C = 256，对于小输入集，它看起来就像 n^2 * lg(n) 。现在将输入集增加到100,000,000； C 的值保持在 256，您现在有 256 * lg (100,000,000)
The value of n depends on the input set, the value of C is fixed.
So yes, if n = 16 and C = 256, it looks like n^2 * lg(n) for a small input set. Now increase the input set to 100,000,000; the value of C stays at 256, you now have 256 * lg (100,000,000)
每当我陷入困境时，我发现将其视为一场竞赛很有用：
我选择一个 big-oh 函数（所以，在你的例子中，logn）和一个常数（c）。重要的是我必须选择一个真正的值。我通常会选择一千个，只是因为。
然后我必须让我的宿敌选择任何他选择的。他通常选择十亿。
然后我做一下比较。
为了完成这个示例，10^9*(log(10^9)) 现在明显比 1000log(10^9) 大得多。因此，我知道大哦行不通。
Whenever I'm stuck on big-oh, I find it useful to think of it as a competition:
I choose a big-oh function (so, in your case, logn) and a constant (c). The important thing is that I have to choose a real value. I usually pick a thousand, just because.
Then I have to let my arch-nemesis pick any n he chooses. He typically chooses a billion.
Then I make the comparison.
To finish the example, 10^9*(log(10^9)) is now made clearly much bigger than 1000log(10^9). Thus, I know that the big-oh won't work.