Найти возможную большую тэту для данной функции времени выполнения f (n) = O (n ^ 2) + nlog (n)?

Question

Предположим, что f ( n ) = O ( n ² ) + n log n . Какие из следующих вариантов возможны?

1. f ( n ) = Θ (log n )
2. f ( n ) = Θ ( n )
3. f ( n ) = Θ ( n ² )
4. f ( n ) = Θ ( n ³ )

Я немного запутался о функции времени выполнения, из-за включенного O ( n ² ). Я считаю, что ответы 2 и 3, потому что каждый из них может быть умножен на число, чтобы достичь O ( n ² ). В частности, Θ ( n ² ) можно умножить на 1 для достижения верхней границы O ( n ² ) и Θ ( n ) можно умножить на n , чтобы достичь верхней границы O ( n ² ).

Am I правильно?

Answer 1

Полагаю, единственный правильный ответ - (3). O(n^2) - это любая функция, которая растет так же быстро, как n^2 или медленнее. n log n = O(n^2), поэтому O(n^2) + n log n - это любая функция, которая асимптотически «между» n log n и n^2. Среди всех тэт в вашем вопросе только третий подходит к этим границам.

Answer 2

Убедитесь, что вы go вернулись к определению большой тэты, отвечая на вопросы такого типа. Чтобы функция f находилась в Θ(g(n)) функции g, необходимо выполнить несколько условий:

1. Существует константа k ₁ , которая больше чем 0
2. Существует константа k ₂ , которая больше 0
3. Существует некоторое начальное значение, n ₀
4. Для всех n> n ₀ , k ₁ * g (n) <= f (n) <= k <sub>2 * g (n)

(4) в основном означает, что с ростом f (n) k ₁ * g (n) растет медленнее и k ₂ * g (n) растет быстрее для того же n.

К счастью, взаимосвязь между этими функциями действительно легко увидеть, когда они изображены рядом друг с другом:)

Ниже мы видим все функции, изображенные рядом друг с другом:

• синий - f(n)
• зеленый - log n
• фиолетовый - n
• черный цвет n^2
• красный цвет n^3

на основании этого графика мы могу я немедленно отбросить log n, n и n^3, потому что нет двух констант , мы могли бы связать эти функции так, чтобы они росли таким образом, чтобы он связывал f(n) с ростом n ,

n^2 однако выглядит многообещающе. Нам просто нужно найти две константы, которые позволяют n^2 ограничить рост f(n).

Ниже мы видим две такие константы:

• синий f(n)
• зеленый 1 * n^2
• фиолетовый * 4 * n^2

Найдя эти константы, мы можем однозначно сказать, что n^2 + n (log n) есть Θ(n^2)

Answer 3

f (n) = O (n ^ 2) + nlogn означает, что в O (n ^ 2) есть ag (n), такое что f (n) = g (n) + nlogn.

g (n) в O (n ^ 2) означает, что | g (n) |

Это означает, что 1, 2, 3 может быть правильным ответом. f (n) не может быть отрицательным, поскольку описывает время работы, но нет причины, по которой термин O (n ^ 2) не может быть отрицательным.

1. g (n) = logn - nlogn - это O (n ^ 2), а g (n) + nlogn = logn.
2. g (n) = n - nlogn - это O (n ^ 2), а g (n) + nlogn = n
3. g (n) = n ^ 2 - nlogn - это O (n ^ 2), а g (n) + nlogn = n ^ 2
4. невозможно.

(Обратите внимание, что вопрос сформулирован в терминах большой тэты, но для f (n) возможно точное совпадение границ в 1, 2 и 3).

3 является единственным решение, если вы предполагаете, что член O (n ^ 2) неотрицателен.