问题描述
我的教授最近对Big O的正式定义一笔带过：
坦率地说，即使在他向几个不同的学生解释之后，我们似乎仍然没有完全理解它的核心。理解上的问题最多出现在我们看过的以下例子中：到目前为止，我的理由如下：
当您将函数的最高项乘以一个常量时，您得到的新函数最终会超过给定n处的初始函数。他将此n称为函数O(g(N))的证人
。如何创建/找到此c术语？他提到了边界几次，但并没有具体说明边界的含义，也没有具体说明如何找到它们/使用它们。
我认为我只需要一个更坚实的正式定义基础，以及这些示例如何支持该定义。
推荐答案
我认为这个定义通常用c值和n0表示，这是不必要的混乱。f(N)是O(g(N))的真正意思是，当你忽略常数和下级项时，g(N)是f(N)的渐近上界(对于g到渐近上界f的函数而言，仅仅意味着超过某一点g总是大于或等于f)。换句话说，当n变为无穷大时，f(N)的增长速度不会快于g(N)。
大O本身有点令人困惑，因为f(N)=O(g(N))并不意味着g(N)严格地比f(N)增长得快。这意味着当你忽略常量和低阶项时，g(N)的增长速度比f(N)快，或者它的增长速度相同(严格地说是更快)。表达这个概念的一种简单、正式的方式是说：也就是说，要使这个极限成立，f(N)的最高阶项至多可以是g(N)的最高阶项的常数倍数。F(N)是O(g(N))当且仅当它的增长不快于g(N)。比如f(N)=n在O(g(N)=n^2)，因为超过某一点n^2总是大于n的，n^2除以n的极限是正的，所以n在O(n^2)
作为另一个例子，f(N)=5n^2+2n在O(g(N)=n^2)中，因为在极限中，f(N)只能大约是g(N)的5倍。它不是无限大的：它们以相同的速度增长。准确地说，n^2除以5n^2+3n的极限是1/5，大于零，所以5n^2+3n在O(n^2)中。希望这个基于限制的定义能提供一些直观的信息，因为它在数学上完全等同于提供的定义。找到给定不等式成立的特定常量值c和x值n0，这只是一种特殊的方式，表明在n趋于无穷大的极限中，g(N)的增长速度至少与f(N)一样快：即f(N)在O(g(N))中。也就是说，如果您已经找到一个c*g(N)始终大于f(N)的值，那么您已经证明f(N)的增长速度不会超过g(N)的常量倍数(c倍)(如果f的增长速度超过g的常量倍数，则不可能找到这样的c和n0)。找出一个特定的c和n0值来证明f(N)=O(g(N))并不是真正的艺术。它们可以是你需要的任何正值，以使不平等成为现实。事实上，如果f(N)=O(g(N))是真的，那么您可以为c选择任何您想要的值，并且将会有一些足够大的N0值使不等式为真，或者，类似地，您可以选择任何您想要的N0值，如果您使c足够大，那么不等式将成为真(遵守c和n0都为正的限制)。这就是为什么我真的不喜欢这种大O的形式化：它是不必要的特别，涉及它的证明有点武断，偏离了主要概念，即当n到无穷大时f和g的行为。那么在实践中如何处理呢，举一个例子：为什么O(n^2)中的n^2+3n是？
回答：因为n的极限是n^2/n^2+3n是1，大于0。
或者，如果您希望/需要以另一种方式执行此操作，则为N0选择任何您想要的正值，并按该值计算f。F(1)总是足够简单：
f(1) = 1^2 + 3*1 = 4
然后找到可以将g(1)乘以得到与f(1)相同的值的常量(或者，如果不使用n0=1，则对g使用您用于f的任何n0)。
c*g(1) = 4
c*1^2 = 4
c = 4
然后，您只需将这些语句组合成一个断言，以表明存在一个正N0和一个常数c，使得对于所有n>；=N0，cg(N)<；=f(N)。
n^2 + 3n <= (4)n^2 for all n >= 1, implying n^2 + 3n is in O(n^2)
如果您使用这种证明方法，那么上面用来证明不等式的语句理想情况下应该是显而易见的。如果不是，也许您想要更改您的N0，以便最后的语句更清楚地为真。我认为，如果您可以使用该路线，则显示g(N)/f(N)的极限为正会更清楚、更直接，但这取决于您。
转到一个负的例子，用极限方法很容易证明f(N)不在O(g(N))中。为此，您只需证明g(N)/f(N)的极限=0。使用第三个示例问题：nlog(N)+2n在O(N)中吗？
要以另一种方式演示它，您实际上必须证明不存在正的数字对N0，c，使得对于所有n>；=N0f(N)<；=Cg(N)。
不幸的是，使用c=2显示f(N)=nlogn+2n在O(Nlogn)中，n0=8没有说明f(N)是否在O(N)中(显示函数在较高复杂度类中并不意味着它不是较低复杂度类)。
要了解为什么会这样，我们还可以使用那些相同的c和n0值(n<；=2(对于所有n>；=8，nlog(N)，暗示n在O(Nlogn))`)来证明a(N)=n在g(N)=nlogn中，但是a(N)=n显然在O(N)中。也就是说，要用这种方法证明f(N)=nlogn+2n在O(N)中不是，不能只证明在O(Nlogn)中是。您必须证明，无论您选择哪一个n0，您都无法找到足够大的c值，使得对于所有n>；=n0，f(N)>；=c(N)。证明这样一对数字不存在并不是不可能的，但相对而言，这是一件棘手的事情(本身可能涉及到极限方程，或者用矛盾来证明)。总而言之，如果g(N)对f(N)的极限为正，则f(N)在O(g(N))中，这意味着f(N)不会比g(N)增长得更快。类似地，找到cg(N)>；=f(N)超过的常数c和x值N0，表明f(N)不能比g(N)渐近增长快，这意味着当丢弃常数和低阶项时，g(N)是f(N)的有效上界。这篇关于在推理大O的形式定义时有点困难的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！