algorithm - 证明 n>=1 或 n>N 的不同定义的 big-Oh 是等价的

Question

我遇到了两个略有不同的 big-oh 定义，需要证明它们彼此等价:

定义 1:f(n) = O(g(n)) 如果存在常数 c 和 N 使得 f(n) ≤ c g(n) 对于所有 n > N。

定义 2:f(n) = O(g(n)) 如果存在一个常数 c 使得 f(n) ≤ c g(n) 对于所有 n≥1。

凭直觉我知道，如果我们选择足够大的 c，我们可以像定义 2 中那样去掉 N。但是如何证明如果定义1蕴含定义2，反之亦然。

Answer 1

它们实际上并不等价，(1) 是正确的定义。

区别的一个例子是在 (1) 下，n = O(n log(n))但根据定义 (2) 它不可能是因为在 n=1因为对于任何 c , c g(n) = c*1*log(1) = 0 < 1 .

之所以 (1) 是正确的定义是因为 big-O 的目的是捕获“接近无穷大”的行为，因此小的特殊情况数量有限 n应该被忽略。

你会看到 (2) 出现的原因是因为它足以建立 big-O。只是没有必要。