Может кто-нибудь объяснить, почему это время работы подходит для этого?

Question

Алгоритм выполняется за время n^2 + 3n + 5 для всех входных данных с размером, большим или равным 500, и за время 2^(2n) для всех входных размеров, меньших 500. Выберите все истинные утверждения снизу:

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

Помните, что нотация big-O говорит только о поведении функции в долгосрочной перспективе. Оглянись на определение:

f (n) = O (g (n)), если существуют числа n₀ и c такие, что для любого n ≥ n₀ имеем f(n) ≤ c·g(n).

В случае вашей функции ваша функция ведет себя односторонне для "маленьких" входов и односторонне для "больших" входов. Обозначение Big-O действительно учитывает только "большой" случай, поэтому вы можете показать, что ваша функция O (n²), потому что для любого n ≥ 500 мы имеем

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

Определение big-Ω работает аналогично - оно учитывает только "достаточно большие" входы, поэтому вы можете сказать, что ваша функция Ω (n²), потому что для любого n ≥ 500 мы имеем

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

Так что это означает, что ваша функция также Θ (n²).

Так что насчет других ответов? Ну, любая функция, которая является O (n²), также является O (4ⁿ), потому что нотация big-O является верхней, а не жесткой границей. Однако это не Θ (4ⁿ), потому что функция не Ω (4ⁿ), поскольку 4ⁿ растет значительно быстрее, чем n^{2 в} долгосрочной перспективе.