如果 f(n) = O(h(n)) 那么对于所有 c > 0 的 c*f(n) = O(h(n)) - 证明受到挑战？
If f(n) = O(h(n)) then c*f(n) = O(h(n)) for all c > 0 - proof challenged?
我被要求证明或反驳以下猜想：
对于任何给定常数 c>0 |如果 f(n) = O(h(n)) 那么 c*f(n) = O(h(n))
我想出了以下反例：
令 f(n) = n 且 c = n+1。然后 c*f(n) = (n+1)n = n^2+n = O(n^2),
而 f(n) = n = O(n)
所以猜想不成立因为O(n^2) != O(n) when f(n) = n and c = n+1.
现在，我得出了以下定理：
Theorem: Any constant value is is O(1).
Aside: You will often hear a constant running time algorithm described
as O(1).
Corollary: Given f(x) which is O(g(x)) and a constant a, we
know that af(x) is O(g(x)).
That is, if we have a function multiplied by a constant, we can ignore
the constant in the big-O.
为什么会这样，我为什么错了？
c 是常量，n 是变量，因此 n+1 不是常量
你没有考虑到足够大的规模：
如果你有一个变量，n乘以常数k和n是增长，k 的影响被最小化。它变成了一个极限问题，来自小学微积分。
我被要求证明或反驳以下猜想：
对于任何给定常数 c>0 |如果 f(n) = O(h(n)) 那么 c*f(n) = O(h(n))
我想出了以下反例：
令 f(n) = n 且 c = n+1。然后 c*f(n) = (n+1)n = n^2+n = O(n^2),
而 f(n) = n = O(n)
所以猜想不成立因为O(n^2) != O(n) when f(n) = n and c = n+1.
现在，我得出了以下定理：
Theorem: Any constant value is is O(1).
Aside: You will often hear a constant running time algorithm described as O(1).
Corollary: Given f(x) which is O(g(x)) and a constant a, we know that af(x) is O(g(x)).
That is, if we have a function multiplied by a constant, we can ignore the constant in the big-O.
为什么会这样，我为什么错了？
c 是常量，n 是变量，因此 n+1 不是常量
你没有考虑到足够大的规模：
如果你有一个变量，n乘以常数k和n是增长，k 的影响被最小化。它变成了一个极限问题，来自小学微积分。