algorithm - 通过归纳法证明多项式 Big-Theta？

Question

我理解大 theta、大 oh 和大 omega 的概念。我只是很难证明它。我已经很长时间没有做归纳了，所以我很确定我只是生疏了，遗漏了一些简单的东西。

例如..我需要帮助的问题是证明5n² - 6n = Θ(n²)。

我已经得到问题的大 O 部分(我分别做大 O 和 Ω 正确吗？):

6k² >= 5n² - 6n

和大欧米茄部分:

5n² - 6n >= n²

....但是我该从这里去哪里呢？!我从归纳中回想起类似...我假设这些是真实的，现在为每个 n 插入 (n+1) 并且...做.. 什么？在这一点上我迷失了自己。

Answer 1

要证明 5n^2-6n 是 O(n^2)，您必须证明以下命题 5n^2-6n <= cn^2 对于所有数字 n >= n0，对于某些数字 n0 和常数 c。

归纳证明涉及证明基本案例的主张和证明归纳步骤。在我们的示例中，我们可以看到基本情况，当 n = 1 时，对于某个常数 c 显然成立。

对于归纳步​​骤，我们假设声明对于某个数字 k 为真，并用它来证明声明对于 k+1 为真。所以我们假设 5k^2-6k <= ck^2 并显示:

5(k+1)^2 - 6(k+1)  = 5k^2 +10k + 5 -6k - 6
                   = 5k^2-6k + 10k -1        
                  <= ck^2 + 10k - 1
                  <= ck^2 + c*2k + c       (for any constant c  >= 5)
                   = c(k+1)^2

这证明了 k+1 的主张并完成了证明。

您可以用类似的方式证明大 Omega 声明。