algorithm - Big O Notation - 自然数 M 和常数因子 C 是什么意思？

Question

在根据代码摘录识别复杂性或最坏情况时，我了解什么是大 O 表示法。

在类里面，我被教导说，当谈到复杂性和大 O 表示法时，我们忽略低于 M 的小参数 n 和常数因子 C 。

这是在类里面给我的:

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)

我可以知道这句话是什么意思吗，特别是:

1. 为什么我们说:

Let f be a function from N to the positive reals.

1. 为什么是指:

Let g be another such function.

1. 这是什么意思:

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)

1. 上述摘录与忽略小参数和常数因子 C 有何关系？

Answer 1

总结: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满足句子。不是:任何 M 也不是任何 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 的所有可能输出的空间。如果我们将 g 的输出空间“扩张”一个常量 C，则它们中的每一个都将大于 f 中的任何一个点。现在这是比我们指定 M 时更强的陈述。如果 f(0) = 10 且 g(0) = 0 会怎样？现在，可以没有 C 使Cg(0) > Cf(0)。因此，M“切断”了这些坏边。

这个页面有很好的解释和视觉效果，还有:https://xlinux.nist.gov/dads/HTML/bigOnotation.html