如何证明1/n是O(1)？

Question

我该如何数学证明1/n是O(1)？我不确定从哪里开始。有什么帮助吗？

- Kazzin

---

你尝试过访问http://en.wikipedia.org/wiki/Big_O_notation吗？ - Pascal Thivent

从证明对于所有的n>1，有1/n <= 1开始（并结束）。 - Sheldon L. Cooper

你确定问题不是“证明 O(1/n) == O(1)”吗？ - Ira Baxter

符号很重要。证明O(1/n)==O(1)并不等于证明1/n运行时间为O(1)。你没有准确表达。那么是哪个？ - Ira Baxter

@IraBaxter 他们有什么不同？1/n是一个函数，所以我认为他们指的是前者，但我不知道你指的后者是什么意思。 - Coder

Answer 1

问题已经说了，从大O符号的定义开始。

F(x) = O(G(x)) IFF there exist constants k and m, 
such that for all n > m, k*|G(n)| > F(n). 

（请参考教科书，以获得精确的措辞。）

简单来说，这意味着如果我们“远离”起点足够远，最终G(n)将主导F(n)，无论我们通过常数因子给予F(n)多大的初始优势。

---

那么，如何证明这样的事情呢？

这种证明通常是建设性的——展示特定的、精心选择的m和k值使不等式成立。

现在你只需要进行代数运算。找到一些能满足正式定义的m和k。根据所需的形式/详细程度，您可能需要证明1/n是单调递减的（或进行归纳证明），以显示您选择的m和k实际上有效。

---

Margus（和Loadmaster）：渐近符号讨论的是函数，与底层硬件和实现完全独立。1/n=O(1)是一个数学真理，甚至不依赖于我们称之为“计算机”的东西的存在。如果您正在考虑指令数量，那么您正在推理复杂度类（考虑P、NP、EXP），而不是渐近符号。

- res

Answer 2

好的，让我们思考一下。我们有两个函数f(n)=1/n和g(n)=1。我们需要两个常数C和k，使得当n>k时，0<=f(n)<=C*g(n)。如果两个函数的定义域都限定在所有正整数的集合中，我们只需选择C=2和k=0。然后我们就有了0<=1/n<=2*1对于所有n>0. 在这里，我们称C和k为关系1/n是O(1)的证明。

需要更严谨地证明吗？嗯...显然，如果且仅如果1<n（通过简单的代数运算）,则1/n<1。因此，如果n=1（这意味着1/n=1），我们知道2*1>1，如果n>1，则这意味着1/n<1，在这种情况下2*1>1/n。

- ClownInTheMoon

Answer 3

如果您正在为算法演示此内容，请首先指出输入将是正数数据（N >= 1），您不能输入1/2的数据 :)

之后，演示当n > 1时，1/n是一个增长函数，您应该对此进行归纳，然后就可以开始了，因为您已经指出n始终大于1！

- David Conde

Answer 4

实际上你不需要证明它，这是一个事实。对于任何大于0的自然数n，1/n的上界始终为1。

- Tokenized man

---

下投票者 - 通常礼貌的做法是留下一条评论解释你为什么要进行负面评价。 @Tokenized man - 我会认为你被投票否决是因为问题已经被证明了，所以它是一个“事实”。OP只是想知道如何证明它自己。 - Austin Hyde

我不是一个点踩的人，但是点踩的可能原因有两个：(1) 这个答案已经被多次提供过了，(2) 这个答案对于那个问问题的人没有帮助，因为这个问题已经十个月前被问过（并且回答过）。 - David Hammen