我一直在尝试掌握大O标记的概念。所以，按照定义大O如下，T(n) ∈ O(G(n)) if T(n) <= G(n) * C。大O标记帮助
由于常数“C”可以是任何> 0的整数，下面的例子也不会是真的吗？
实施例：
n log n ∈ O(log n)
n log n <= log n * c
其中C等于n的值。
我知道答案是n log n ∉ O(log n)但我不明白如何，因为C可以是任何常数。
在此先感谢您的帮助：d
c是仅仅是一个不断。这意味着你不能说“让c是n的值”，因为你必须首先选择一些c，然后让这个比较适用于所有的n。换句话说，为了使一些T（n）为O（G（n）），必须存在常数c，使得G（n）* c大于T（n）全部
因此，n log n不是O（log n），因为无论选择什么常数，n> c都会导致n log n大于c log n。
让我重复你的话。
c可以是任何常数。
这意味着c不能依赖于n。
这个想法是不等式成立的任何n和一个固定 c。所以虽然你可能会发现某个特定的c，使得n log n（即任意c> n），你可以很容易地找到其他不适用的n'（即n'> c）。
我认为这种误解的根源在于你选择了c *在某些*点。但那是每个功能类的一次，而不是每n次。 – Nicolas78 2010-07-28 15:53:29
在定义中，您应该仅由T和G本身来确定C.这是一个常数C的意思。所以C不应该依赖于它们的输入。所以你不能在表达式n log n中考虑C = n
，你不能比较外部的n和C，就像你在做什么一样。这就像使用algrebraic表达式x（x + 1）并用一个常量替换其中一个x。
在n log n中，n是一个变量。在大O表达式中，C是一个常数。
n的值取决于输入集，C的值是固定的。因此，如果n = 16且C = 256，对于小的输入集看起来像n^2 * lg（n）。现在将投入增加到100,000,000; C的值保持在256，你现在有256 * lg（100,000,000）
首先，如果n = C，那么C不是常数。在大多数现实世界的算法中，C很小，所以大O部分通常支配n的典型值。
但是，大O复杂性与大n的算法的效率有关，特别是当n接近无穷大时。换句话说，它告诉你算法的可扩展性：给定算法处理非常大或者加倍的工作负载的能力。
如果你知道n是总是小，那么大O的复杂性就不那么重要了，而应该关注算法所需的挂钟时间。此外，如果您在两个具有相同大O复杂度的算法（例如O（n log n））之间进行选择，通常一个比另一个更好（例如随机数据透视快速排序通常优于二进制堆排序）。
“，在大多数现实世界的算法中，c很小，所以大O部分通常支配n”的典型值：这是令人困惑的一个c-用于确定某个算法是O（某物）的常数 - 完全不同的c，程序运行时的常数因子（即运行时间= 3X + c）。这些不一样。 – Borealid 2010-07-27 20:09:30
OP使用“C”作为乘法因子，而不是常量附加项。我只是使用相同的语言（抱歉小写字母“c”）。 – Qwertie 2010-07-28 15:38:14
这不是我的意思。而且，实际上，在原始问题中使用了小写'c'。仔细阅读我所选择的句子，你会发现它不能指OP任务中的任意乘法常数 - 因为OP的'c'是一个选择的反例，而不是“真实世界算法”的一个因素。 “在大多数现实世界算法中c很小”是指运行时系数。 – Borealid 2010-07-28 16:52:47
每当我被困在大哦，我觉得它是有用的认为它是一个竞争： 我选择一个大哦功能（所以，你的情况，logn）和一个常数（c）。重要的是我必须选择一个真正的价值。我通常选择一千个，只是因为。 然后，我必须让我的拱手报仇任何他选择。他通常选择十亿。
然后我进行比较。为了完成这个例子，10^9 *（log（10^9））现在明显比1000log（10^9）大得多。因此，我知道这个大哦不行。
这功课吗？ – 2010-07-27 19:28:04
@Jacob，显然。不过，这并不是一个坏问题。 bigO是每个程序员都应该理解的东西。 – 2010-07-27 19:30:53
@Byron，绝对。 – 2010-07-27 19:31:25