我一直在努力理解大O符号的概念，根据定义，大O表示如下：T(n) ∈ O(G(n)) if T(n) <= G(n) * C。
由于常数"C"可以是任何大于0的整数，那么下面的例子也是正确的吗？
例子：
n log n ∈ O(log n)
n log n <= log n * c
其中C等于n的值。
我知道答案是n log n ∉ O(log n)，但我不明白为什么，因为C可以是任何常数。
非常感谢您的帮助:D
帮助理解大O符号表示法
9
- Steven
4
3@Jacob，显然。但这并不意味着这是一个糟糕的问题。bigO是每个程序员都应该理解的东西。 - Byron Whitlock
不是作业，只是在期中考试前澄清一些事情。 - Steven
1@Steven，我希望当我还在上大学的时候，互联网（特别是SO）已经存在了。这会为我节省很多时间，不用在地下室的科学楼里的计算机科学图书馆里度过许多个小时。祝你考试好运！ - Byron Whitlock
1谢谢Byron，也再次感谢大家提供这么好的答案:D - Steven
8个回答
11
c就是一个常数。这意味着你不能说“让c成为n的值”，因为你必须先选择一些c，然后才能允许比较在所有n中都成立。
换句话说，为了使某个T(n)成为O(G(n)), 必须不存在任何常数c使得对于所有n，G(n)*c大于T(n)。
因此，n log n不是O(log n)，因为无论你选择什么常数，n > c将导致n log n大于c log n。
- Borealid
4
让我重复一下你的话。
c可以是任何一个常数。
这意味着c不能依赖于n。
- mik01aj
4
这个想法是对于任何n和一个固定的c，不等式都成立。所以虽然你可能会发现某个c，使得n log n < c log n（即任何c> n），但你也可以很容易地找到其他n’，它并不成立（即n'>c）。
- Nicolas78
1
我认为这个误解的根源在于你在某个时候选择了c。但是这只发生在每个函数类中一次，而不是每个n中一次。 - Nicolas78
2
首先，如果n=C，则C不是常数。在大多数实际算法中，C很小，因此对于典型的n值，大O部分通常占主导地位。
但是，大O复杂度关注的是算法在大n下的效率，特别是当n接近无限大时。换句话说，它告诉您算法的可伸缩性：给定算法如何处理非常大或加倍的工作负载。
如果您知道n始终很小，则大O复杂度并不重要，而应该专注于算法所需的挂钟时间。此外，如果您在两个具有相同大O复杂度（例如O（n log n））的算法之间进行选择，通常情况下一个比另一个更好（例如，随机枢轴快速排序通常优于二叉堆排序）。
但是，大O复杂度关注的是算法在大n下的效率，特别是当n接近无限大时。换句话说，它告诉您算法的可伸缩性：给定算法如何处理非常大或加倍的工作负载。
如果您知道n始终很小，则大O复杂度并不重要，而应该专注于算法所需的挂钟时间。此外，如果您在两个具有相同大O复杂度（例如O（n log n））的算法之间进行选择，通常情况下一个比另一个更好（例如，随机枢轴快速排序通常优于二叉堆排序）。
- Qwertie
5
在大多数实际算法中，c很小，因此对于典型的n值，大O部分通常占主导地位。这会让人感到困惑，因为一个用于确定某个算法是O（某事物）的常数c与程序运行时间中的完全不同的常数因子c（即runtime = 3X + c）被混淆了起来。它们并不相同。 - Borealid
原帖中使用了 "C" 作为乘法因子，而不是常数项。我只是使用了相同的语言（抱歉小写的 "c"）。 - Qwertie
这不是我的意思。实际上，在原始问题中使用了小写字母'c'。仔细阅读我选择的句子，你会发现它不能指代来自OP帖子的任意乘法常数 - 因为OP的'c'是一个选择的反例，而不是“真实世界算法”的因子。“在大多数真实世界算法中，c很小”是指运行时间系数。 - Borealid
@Borealid：不，我还是不明白你为什么在谈论一个加法“+c”。 - Qwertie
如果一个算法在n个元素上执行n+k次操作，那么它是O(n)。证明它是O(n)的方法是说“不存在X使得对于所有n，Xn > j(n+k)”。当你说“在大多数实际算法中，C很小”时，你必须引用实际运行时间的常数因子（上面的k）。它不能是存在变量（上面的X）或存在常数（j），因为这些不存在于“实际算法”中。但是你说“如果n=C，则C不是常数”。因此，在你的前两句话中，你有些困惑。 - Borealid
1
在定义中，您应该仅通过 T 和 G 自身来确定 C。这就是常数 C 的含义。因此，C 不应取决于它们的输入。因此，您不能将 C 视为等于 n。
- Shayan
1
在表达式n log n中，您不能像您所做的那样将外部的n与C进行比较。这就像用常数替换代数表达式x（x + 1）中的一个x一样。
在n log n中，n是一个变量。在大O表达式中，C是一个常数。
在n log n中，n是一个变量。在大O表达式中，C是一个常数。
- hvgotcodes
1
n的值取决于输入集合，而C的值是固定的。
因此，如果n = 16且C = 256，则对于小型输入集合，它看起来像是n^2 * lg(n)。现在将输入集合增加到100,000,000；C的值保持为256，你现在有256 * lg(100,000,000)。
- BrianH
1
每当我在大O符号上遇到困难时，我发现将其视为一场比赛很有用：
我选择一个大O函数（所以，在你的情况下，是logn）和一个常数（c）。重要的是我必须选择一个实际值。通常我选择一千，只是因为这个数字。
然后，我必须让我的劲敌选择 他想要的任何n。他通常会选择十亿。
然后我进行比较。
为了完成这个例子，10^9*(log(10^9)) 现在显然比 1000log(10^9) 要大得多。因此，我知道大O符号不起作用。
- agorenst
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接