Big O Notation - 自然数 M 和常数因子 C 是什么意思？
Big O Notation - what does the natural number M and constant factor C mean?
在根据代码摘录识别复杂性或最坏情况时，我了解什么是大 O 表示法。
在 class 中，我被教导说当谈到复杂性和大 O 表示法时，我们忽略低于 M 的小参数 n 和常数因子 C.
这是在 class 中给我的：
In Big-Oh notation. Let f be a function from N to the positive reals.
(Think of f(n) as the running time for an argument of size n. It could
be worst case or it could be average case.) Let g be another such
function. We say that f ∈ O(g) when there is some natural number M and
constant factor C, such that for all n > M, we have f(n) <= C × g(n).
In logical symbols: ∃M. ∃C. ∀n > M. f(n) <= C × g(n)
请问这句话是什么意思，具体来说：
- 为什么我们说：
Let f be a function from N to the positive reals.
- 为什么意思是：
Let g be another such function.
- 什么意思：
We say that f ∈ O(g) when there is some natural number M and
constant factor C, such that for all n > M, we have f(n) <= C × g(n).
In logical symbols: ∃M. ∃C. ∀n > M. f(n) <= C × g(n)
- 以上摘录与忽略小参数和常数因子 C 有何关系？
对于 (1) 和 (2)：通常，在证明或定义中，文本 Let x be a Y 是证明 all x满足条件Y的还有一个属性 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 "bigger" 的想法。除了，我们关心的是 f 和 g 的最终行为，而不是它们对小值的行为。因此，在语句中添加 ∃M。那就是说 最终 g 比 f 大。而且，我们更感兴趣的是 f 和 g 的 "shape"，它给了我们常量 C.
一个有启发性的练习是用双重否定重写语句：
~ ~ ∃M. ∃C. ∀n > M. f(n) <= C × g(n)
然后通过语句推第二个否定：
~ ∀M. ∀C. ∃n > M. f(n) > C × g(n)
然后考虑第一个否定中的语句是什么意思。
总结一下：C乘以g 最终支配 f.
1 & 2.
Let f be a function from N to the positive reals. (Think of f(n) as the running time for an argument of size n. It could be worst case or it could be average case.) Let g be another such function.
OK：f和g是从自然数（N）到正实数的函数。为什么来自自然数？我们假设参数的大小是我们可以精确指定的。自然数是我们可以精确指定的东西。实数不是。为什么是正实数？我们假设 运行 时间不一定是我们可以精确指定的时间。
但这里重要的实际上不是说了什么，而是没有说了什么。没有人说 f 是单调递增的，或者 g 是多项式，或者其他什么。我们所知道的是 f 和 g 是 函数 。这几乎就是它的全部。是的，它们从自然数映射到正实数，但就限制而言，这是一个相当小的限制。所以这里的重点是：有很多很多函数 f 和 g 可供选择。唯一有点重要的限制是实数比自然数多得多。
3.
We say that f ∈ O(g) when there is some natural number M and constant factor C, such that for all n > M, we have f(n) <= C × g(n). In logical symbols: ∃M. ∃C. ∀n > M. f(n) <= C × g(n)
M和C是常量。我们选择 M 和 C，我们就完成了。这里重要的一点是至少有一个 M和至少有一个C满足句子。不是：any M 也不是any C。声明是有至少一个这样的M和C.
另一方面，n 不是常数。我们可以选择 n 为任何数，只要它大于 M。声明说对于 any 选择 n（大于 M），C 的至少一个值可以是发现，所以如果你将 g(n) 乘以 C，这个乘积将大于 f(n)。 n 是什么并不重要，只要它比 M 大即可。
当我们假设解除了其中一个限制时，我们考虑常数 M 和 C 的原因就变得清楚了。假设语句没有提到 M:
We say that f ∈ O'(g) when there is some constant factor C, such that for all n, we have f(n) <= C × g(n). In logical symbols: ∃C. ∀n f(n) <= C × g(n)
现在这表示：考虑 f 的所有可能输出和 g 的所有可能输出的 space。如果我们 "dilate" g 输出的 space 乘以常数 C，则它们中的每一个都将大于 f 中的任何一个点。现在这是比我们指定 M 时更强的陈述。如果 f(0) = 10 且 g(0) = 0 会怎样？现在，可以有没有 C 使得Cg(0) > Cf(0)。所以，M"cuts off"这些坏边。
这个页面有很好的解释和视觉效果，还有：https://xlinux.nist.gov/dads/HTML/bigOnotation.html
在根据代码摘录识别复杂性或最坏情况时，我了解什么是大 O 表示法。
在 class 中，我被教导说当谈到复杂性和大 O 表示法时，我们忽略低于 M 的小参数 n 和常数因子 C.
这是在 class 中给我的：
In Big-Oh notation. Let f be a function from N to the positive reals. (Think of f(n) as the running time for an argument of size n. It could be worst case or it could be average case.) Let g be another such function. We say that f ∈ O(g) when there is some natural number M and constant factor C, such that for all n > M, we have f(n) <= C × g(n). In logical symbols: ∃M. ∃C. ∀n > M. f(n) <= C × g(n)
请问这句话是什么意思，具体来说：
- 为什么我们说：
Let f be a function from N to the positive reals.
- 为什么意思是：
Let g be another such function.
- 什么意思：
We say that f ∈ O(g) when there is some natural number M and constant factor C, such that for all n > M, we have f(n) <= C × g(n). In logical symbols: ∃M. ∃C. ∀n > M. f(n) <= C × g(n)
- 以上摘录与忽略小参数和常数因子 C 有何关系？
对于 (1) 和 (2)：通常，在证明或定义中，文本 Let x be a Y 是证明 all x满足条件Y的还有一个属性 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 "bigger" 的想法。除了，我们关心的是 f 和 g 的最终行为，而不是它们对小值的行为。因此，在语句中添加 ∃M。那就是说 最终 g 比 f 大。而且，我们更感兴趣的是 f 和 g 的 "shape"，它给了我们常量 C.
一个有启发性的练习是用双重否定重写语句：
~ ~ ∃M. ∃C. ∀n > M. f(n) <= C × g(n)
然后通过语句推第二个否定：
~ ∀M. ∀C. ∃n > M. f(n) > C × g(n)
然后考虑第一个否定中的语句是什么意思。
总结一下：C乘以g 最终支配 f.
1 & 2.
Let f be a function from N to the positive reals. (Think of f(n) as the running time for an argument of size n. It could be worst case or it could be average case.) Let g be another such function.
OK：f和g是从自然数（N）到正实数的函数。为什么来自自然数？我们假设参数的大小是我们可以精确指定的。自然数是我们可以精确指定的东西。实数不是。为什么是正实数？我们假设 运行 时间不一定是我们可以精确指定的时间。
但这里重要的实际上不是说了什么，而是没有说了什么。没有人说 f 是单调递增的，或者 g 是多项式，或者其他什么。我们所知道的是 f 和 g 是 函数 。这几乎就是它的全部。是的，它们从自然数映射到正实数，但就限制而言，这是一个相当小的限制。所以这里的重点是：有很多很多函数 f 和 g 可供选择。唯一有点重要的限制是实数比自然数多得多。
3.
We say that f ∈ O(g) when there is some natural number M and constant factor C, such that for all n > M, we have f(n) <= C × g(n). In logical symbols: ∃M. ∃C. ∀n > M. f(n) <= C × g(n)
M和C是常量。我们选择 M 和 C，我们就完成了。这里重要的一点是至少有一个 M和至少有一个C满足句子。不是：any M 也不是any C。声明是有至少一个这样的M和C.
另一方面，n 不是常数。我们可以选择 n 为任何数，只要它大于 M。声明说对于 any 选择 n（大于 M），C 的至少一个值可以是发现，所以如果你将 g(n) 乘以 C，这个乘积将大于 f(n)。 n 是什么并不重要，只要它比 M 大即可。
当我们假设解除了其中一个限制时，我们考虑常数 M 和 C 的原因就变得清楚了。假设语句没有提到 M:
We say that f ∈ O'(g) when there is some constant factor C, such that for all n, we have f(n) <= C × g(n). In logical symbols: ∃C. ∀n f(n) <= C × g(n)
现在这表示：考虑 f 的所有可能输出和 g 的所有可能输出的 space。如果我们 "dilate" g 输出的 space 乘以常数 C，则它们中的每一个都将大于 f 中的任何一个点。现在这是比我们指定 M 时更强的陈述。如果 f(0) = 10 且 g(0) = 0 会怎样？现在，可以有没有 C 使得Cg(0) > Cf(0)。所以，M"cuts off"这些坏边。
这个页面有很好的解释和视觉效果，还有：https://xlinux.nist.gov/dads/HTML/bigOnotation.html