algorithm - Big-O 表示法和多项式？

Question

所以我有这个问题要做，我不确定从哪里开始：

使用 Big-O 的定义，证明以下内容：

1. T(n) = 2n + 3 ∈ O(n)
2. T(n) = 5n + 1 ∈ O(n ² )
3. T(n) = 4n ² + 2n + 3 ∈ O(n ² )

如果有人能指出我正确的方向（你不一定要给我确切的答案），我将不胜感激。

Answer 1

您可以使用相同的技巧来解决所有这些问题。作为提示，请使用以下事实

如果 a ≤ b，则对于任何 n ≥ 1，n ^a ≤ n ^b。

例如，您可以通过以下方式处理其中的第一个：如果 n ≥ 1，则 2n + 3 ≤ 2n + 3n = 5n。因此，如果你取 n ₀ = 1 和 c = 5，那么对于任何 n ≥ n ₀ ，你都有2n + 3 ≤ 5n。因此，2n + 3 = O(n)。

尝试使用类似的方法来解决其他问题。对于第二个问题，您可能想要使用它两次 - 一次使用某个线性函数对 5n + 1 进行上限，再一次使用某个二次函数对该线性函数进行上限。

希望这可以帮助！