big-o - 大 O 符号和规则

Question

我了解添加功能时，行为以最高功率为主。但是我很难理解这个证明。谁能帮我一步一步解释背后的证明

T1(n) + T2(n) => O(max (f(n), g(n)))

非常感谢

Answer 1

符号 f(n) = O(g(n)) 实际上是以下的简写：

存在 N > 0 和 c > 0 使得对于所有 n > N，f(n) ≤ cg(n)。

f(n) = O(g(n)) 中的等号实际上是对符号的滥用；它实际上意味着 f∈O(g)，尽管实际上没有人这么写。所以，我们有明显的

n = O(n),

1000 n = O(n),

乃至

1000 n = O(n²)。

请注意，这并不意味着 O(n) = O(n²)，将 O(n) 和 O(n²) 视为函数集；与等式不同，使用 O 表示法的表达式不是自反的。任何 O(n) 函数都是 O(n²)，但不是相反。

所以，作为一个例子，我们将展示

n³ + 1000 n² + 10000 = O(n³)。

令 N 为最大系数：N = 10000。然后，对于 n > N，

n³ + 1000 n² + 10000 < n³ + N n² + N < n³ + n n² + n < n³ + n³ + n³ = 3 n³。

多项式由最高次项支配。现在，您的问题的解决方案很明确。

如果 T₁(n) = O(f(n))，则存在 N₁ 和 c₁，使得对于所有 n > N₁，T₁(n) ≤ c₁ f(n)。

如果 T2(n) = O(g(n))，则存在一个 N2 和一个 c2，使得对于所有 n > N2，T2(n) ≤ c2 g(n)。

令 c = max(c₁, c₂) 和 N = max(N₁, N₂)。然后，对于 n > N，

T₁(n) + T₂(n) ≤ c₁ f(n) + c₂ g(n)

≤ cf(n) + cg(n) = c (f(n) + g(n))

≤ c ⋅ (2 max(f(n), g(n))) = 2c max(f(n), g(n))。

如果您在微积分中完成了 ε-δ 证明，它会有所帮助。