在基于代码摘录识别复杂性或最坏情况时，我理解Big O Notation是什么。
在课堂上，我被教导说，当涉及复杂性和大O符号时，我们忽略低于n和常数因子M的小参数C。
这是在课堂上给我的：
用Big-Oh表示法。设f是从N到正实数的函数。 （将f（n）视为大小为n的参数的运行时间。可能是最坏情况或者可能是平均情况。）设g是另一个这样的函数。当存在一些自然数M和常数因子C时，我们说f∈O（g），使得对于所有n> M，我们有f（n）<= C×g（n）。在逻辑符号中：∃M。 ∃C。 ∀n> M. f（n）<= C×g（n）
我可以知道这句话是什么意思，具体来说：
设f是从N到正实数的函数。
设g是另一个这样的函数。
当存在一些自然数M和常数因子C时，我们说f∈O（g），使得对于所有n> M，我们有f（n）<= C×g（n）。在逻辑符号中：∃M。 ∃C。 ∀n> M. f（n）<= C×g（n）
总结一下：C次g最终支配f。
1 & 2.
设f是从N到正实数的函数。 （将f（n）视为大小为n的参数的运行时间。可能是最坏情况或者可能是平均情况。）设g是另一个这样的函数。
好的：f和g是从自然数（N）到正实数的函数。为什么来自自然数？我们假设参数的大小是我们可以精确指定的。自然数是我们可以精确指定的。实数不是。为什么要积极实力？我们假设运行时间不一定是我们可以精确指定的。
但重要的是，实际上并不是说什么，而是说什么。没有人说f是单调递增的，或者g是多项式，或者其他什么。我们所知道的是f和g是函数。这几乎就是它的全部内容。是的，它们从自然界映射到积极实际，但就限制而言，这是一个非常小的限制。所以这里的重点是：有很多很多函数f和g可供选择。唯一有点重要的限制是，实物比自然更多。
3.
当存在一些自然数M和常数因子C时，我们说f∈O（g），使得对于所有n> M，我们有f（n）<= C×g（n）。在逻辑符号中：∃M。 ∃C。 ∀n> M. f（n）<= C×g（n）
M和C是常数。我们选择M和C，我们完成了。这里重要的一点是，至少有一个M和至少一个C满足该句子。不是：任何M或任何C.声明是至少有一个这样的M和C.
另一方面，n不是常数。我们可以选择n为任何数，只要它大于M.声明说，对于任何n（大于M）的选择，至少可以找到一个C的值，所以如果你乘以g（n） ）通过C，该产品将大于f（n）。 n是什么并不重要，只要它大于M.
当我们假设其中一个限制被解除时，我们认为常数M和C变得清晰的原因。假设声明中没有提到M：
我们说f∈O'（g）当存在一些常数因子C时，对于所有n，我们得到f（n）<= C×g（n）。在逻辑符号中：∃C。 ∀nf（n）<= C×g（n）
现在这说：考虑f的所有可能输出的空间和g的所有可能输出。如果我们将g的输出空间“扩大”一个常数C，那么它们中的每一个都将大于f中的任何一个点。现在这是一个比我们指定M更强的陈述。如果f（0）= 10且g（0）= 0，该怎么办？现在，没有C可以制作Cg(0) > Cf(0)。所以，M“切断”这些坏边缘。
这个页面有一个很好的解释和视觉，以及：https://xlinux.nist.gov/dads/HTML/bigOnotation.html
对于（1）和（2）：通常，在证明内或定义内，文本Let x be a Y是证明满足条件Y的所有x具有附加属性Z的证明的一部分。证明将证明结论Z对于X是正确的。然后，因为除了Y之外没有在X上指定条件，所以得出结论，对于具有条件Y的所有X，条件Z也为真。
你必须自己完成（3）。除了将该陈述分解为更小的部分，理解每个部分，然后将它们组合在一起以理解整个陈述之外，没有其他替代品。
对于（4）：常量C出现在语句本身中，特别重要的是C出现一个存在性限定符：
∃C. ∀n > M. f(n) <= C × g(n)
这在声明中给出了C含义。为了表达意思，我们最好看一下整个陈述：
∃M. ∃C. ∀n > M. f(n) <= C × g(n)
在本声明的中心，我们想表达g比f更“大”的想法。除此之外，我们关注的是f和g的最终行为，而不是它们对小值的行为。因此，在声明中增加了∃M。这就是说最终g大于f。而且，我们对f和g的“形状”更感兴趣，它给了我们恒定的C.
一个有益的练习是用双重否定重写声明：
~ ~ ∃M. ∃C. ∀n > M. f(n) <= C × g(n)
然后通过声明推动第二次否定：
~ ∀M. ∀C. ∃n > M. f(n) > C × g(n)
然后考虑第一个否定意味着什么。