algorithm - 有人可以解释一下为什么二次函数在 Θ(n²) 中的具体证明吗？

Question

我需要对算法介绍中第 3 章的这一部分进行解释。

例如，考虑任何二次函数 f(n) = an² + bn + c，其中 a、b 和 c 是常数且 a > 0。丢弃低阶项并忽略常数产生 f(n) = Θ(n²)。形式上，为了说明同样的事情，我们取常数 c₁ = a/4、c₂ = 7a/4 和 n₀ = 2·max(|b|/a, √(|c|/a))。对于所有 n ≥ n₀，您可以验证 0 ≤ c₁n² ≤ an²+bn+c ≤ c₂n²。

对我来说，任何二次函数都是 Θ(n²) 是完全有道理的，因为你去掉了低阶项和最高阶项的系数。但是，在这个证明中，为什么要为 c₁、c₂ 和 n₀ 选择这些常数值？它们看起来很随意，但也许我缺少一些东西。我通常理解 Θ 的定义，但不理解这个证明，因为它与二次函数有关。

标签： algorithmbig-o

Answer 1

这些参数似乎是任意的，因为它们是。该定义仅说明存在此类参数，并且通常有很多参数有效。只需选择 a并为该特定c计算 a 。nc