algorithm - 大 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

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

If a ≤ b, then for any 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 的上限，然后再一次使用一些二次函数使用该线性函数的上限。

希望这对您有所帮助!