big-o - 如何证明使用 big-O

Question

我目前遇到大 O 表示法的问题。我有以下我想弄清楚的问题。

我目前有公式：T(n) 是 O(f(n))，我必须用它来直接从大 O 的定义中证明 3n^2+11n+6 是 O(n^2)。

我想知道是否有人可以帮助我解决这个问题，因为我无法解决这个问题。

标签： big-o

Answer 1

我认为这可能会有所帮助：对于 n≥k，有一个常数，我们将其命名为“c”，它满足 3n^2 + 11n + 6 ≤ c∗n^2。假设我们选择 k = 1。我们知道 n^2 ≥ n^2 ≥ n ≥ 1

所以 ：
3n^2 + 11n + 6 ≤ 3n^2 + 11n^2 + 6n^2 =>3n^2 + 11n + 6 ≤ 20n^2

现在，让 c = 20。=> 复杂度为 O(n2)。