有人可以解释为什么这些 运行 时间适合这个吗？

Question

对于大小大于或等于 500 的所有输入，算法在时间 n^2 + 3n + 5 中运行，对于所有大小小于 500 的输入，算法在时间 2^(2n) 中运行。Select 所有以下陈述为真：

1: Its running time is O(2^(n))
2: Its running time is O(n^(2))
3: Its running time is Θ(n^(2))
4: Its running time is Θ(2^(2n))
5: Its running time is O(4^(n))
6: Its running time is Ω(n^(2))

正确答案是：1、2、3、5、6

我不知道所有这些都是如何解决上述问题的，请帮助！

Answer 1

请记住，大 O 表示法只讨论函数的长期行为。回头看定义：

f(n) = O(g(n)) if there are numbers n₀ and c such that for any n ≥ n₀, we have f(n) ≤ c·g(n).

就您的函数而言，您的函数对 "small" 输入表现一种方式，对 "large" 输入表现一种方式。大 O 符号只会真正考虑 "large" 的情况，所以你可以证明你的函数是 O(n²)，因为对于任何 n ≥ 500，我们有

f(n) = n² + 3n + 5 ≤ 5n².

big-Ω 的定义以同样的方式工作——它只考虑 "sufficiently large" 个输入，所以你可以说你的函数是 Ω(n²) 因为对于任何 n ≥ 500，我们有

f(n) = n² + 3n + 5 ≥ n².

所以这意味着你的函数也是 Θ(n²)。

那么其他答案呢？好吧，任何 O(n²) 的函数都是 also O(4ⁿ) 因为大- O 表示法是上界，而不是紧界。然而，它不是 Θ(4ⁿ)，因为函数不是 Ω(4ⁿ) 因为 4ⁿ 的增长速度远快于 n²。