algorithm - 渐近符号：找到两个常数，使得 n >= n0
问题描述
这是一个渐近符号问题：
令 g(n) = 27n^2 + 18n 并令 f(n) = 0.5n^2 − 100。找到正常数 n0、c1 和 c2 使得 c1f(n) ≤ g(n) ≤ c2f(n) 为所有 n ≥ n0。
这是解决 theta 问题吗？我要证明 27n^2 + 18n = Ω(0.5n^2 - 100)，然后证明 (27n^2 + 18n) = O(0.5n^2 - 100)？
在那种情况下，c1 和 c2 不会分别是 1 和 56，而 n0 会是我找到的两个 n0 中的较高者吗？
解决方案
有无限多的解决方案。我们只需要摆弄代数就可以找到一个。
首先要注意的是，对于所有 n≥15，g 和 f 都是正数。特别是，g(15) = 6345，f(15) = 12.5。（所有较小的 n 值使 f<0。）这意味着 n0=15 可能与任何较大的值一样工作正常。
下注 g'(n) = 54n + 18 和 f'(n) = n。
由于对于所有 n >= 15，f(15) < g(15) 和 f'(n) < g'(n)，因此选择 c1 = 1。
证明这是一个不错的选择：
0.5n^2 - 100 ≤ 27n^2 + 18n <=> 26.5n^2 + 18n + 100 ≥ 0
...显然对于所有 n≥15 都是正确的。
c2呢？首先，我们希望 c2*f(n) 的增长速度至少与 g 一样快：c2f'(n)≥g'(n)，或者对于 n ≥ 15，c2*n ≥ 54n + 18。所以选择 c2 ≥ 56，这显然使这成为现实。
不幸的是，c2=56 在 n0 = 15 时不太适用。还有另一个标准要满足：c2*f(15)≥g(15)。为此，56 还不够大：56*f(15) 只有 700；g(15) 要大得多。
事实证明，通过上面关系中的替换和更多的代数，c2 = 508 可以解决问题。
证明：
27n^2 + 18n ≤ 508 * (0.5n^2 - 100)
<=> 27n^2 + 18n ≤ 254n^2 - 50800
<=> 227n^2 - 18n - 50800 ≥ 0
在 n=15 时，通过简单的替换是正确的。对于所有较大的 n 值，请注意 lhs 导数 454n - 18 对于所有 n≥15 都是正数，因此该函数在该域上也是非递减的。这也使关系成立。
总而言之，我们已经证明n0=15、c1=1 和 c2=508是一种解决方案。