如何数学证明1 / n是O(1)？我对从哪里开始感到困惑。有什么帮助吗？
最佳答案
就像问题所言，先从big-O符号的定义开始。
F(x) = O(G(x)) IFF there exist constants k and m,
such that for all n > m, k*|G(n)| > F(n).
(请咨询您的textboox以获取准确的用词。)
非正式地讲，这意味着如果我们走得足够远，最终G(n)将支配F(n)，无论我们通过常数因子赋予F(n)多少初始优势。
那么，您如何证明这样的事情？
像这样的证明通常是 build 性地完成的-表明m和k的特定选择值使不等式起作用。
现在您正在做代数。找到一些满足形式定义的m和k。根据所需形式/细节的级别，您可能需要证明1 / n单调递减(或做一些归纳证明)以表明您对m和k的选择确实有效。
Margus(和Loadmaster):渐近表示法讨论功能，并且完全独立于底层硬件和实现。 1 / n = O(1)是一个数学真理，即使存在我们称为“计算机”的事物，也无法确定。如果您在考虑指令的数量，那么您就在考虑复杂性类(请考虑P，NP，EXP)，而不是渐进表示法。
关于math - 如何证明1/n是O(1)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3800651/