Биг-О нотация, найти самый маленький

Question

Дайте наименьшую оценку O (), которую вы можете выполнить для следующих функций:

4n2 + 5n – 8 = O(...)


log(n)2 + n = O(...)

Если вы, ребята, можете, объясните ответ, а не дайте его мне. Подобный вопрос будет в моем среднесрочном семестре, и я хочу это понять.

Спасибо

Answer 1

Когда вы имеете суммы терминов, вы должны думать о них как о том, что «один термин включает в себя другой?».Итак, какой из 4n ² , 5n и 8 включает остальные?

Второй: log (n) ² + n может быть переписан с использованием логарифмических законов:2 * LOG (п) + N.Константы не имеют значения, поэтому в основном вы должны выяснить, какая из них объединяет другую при сравнении log (n) и n .Я уверен, что вы знаете ответ здесь; -)

Answer 2

Обозначение Big-O упорядочено с возрастающей сложностью, как описано здесь на http://en.wikipedia.org/wiki/Big_O_notation,, у них есть хорошая таблица, показывающая упорядоченный список растущих сложностей, если у вас есть какие-либо дополнительные вопросы по этому поводу / вы не уверены в чем-то.

Answer 3

При суммировании уравнений: выберите самое тяжелое. (Самый большой в асимптотическом порядке).

Если вы хотите проверить, как это работает с алгеброй, или какая-то поддержка CAS, проверьте этот ответ .

Answer 4

Запись неверна. Функция не равно классу O, функция элемент класса O