Биг-О нотация, найти самый маленький
Дайте наименьшую оценку O(), которую вы можете выполнить для следующих функций:
4n2 + 5n – 8 = O(...)
log(n)2 + n = O(...)
Если вы, ребята, можете, объясните ответ, а не дайте его мне. Такой вопрос будет на моем среднесрочном плане, и я хочу это понять.
Спасибо
4 ответа
Имея суммы терминов, вы должны думать об этом как "один термин относится к другому?". Итак, какой из 4n2, 5n и 8 включает остальные?
Второй: log(n)2+ n можно переписать с использованием логарифмических законов: 2*log(n)+n. Константы не имеют значения, поэтому в основном вы должны выяснить, какая из них включает другую при сравнении log(n) и n. Я уверен, что вы знаете ответ здесь;-)
Нотация Big-O упорядочена в возрастающей сложности, как описано здесь на http://en.wikipedia.org/wiki/Big_O_notation, у них есть хорошая таблица, показывающая упорядоченный список растущих сложностей, если у вас возникли дополнительные вопросы по этому поводу / были не уверен в чем-то.
Запись неверна. Функция не равна классу O, функция является элементом класса O
При суммировании уравнений: выберите самый тяжелый. (Самый большой в асимптотическом порядке).
Если вы хотите узнать, как это работает с алгеброй или какой-либо поддержкой CAS, ознакомьтесь с этим ответом.