Как правильно найти порядок роста для этой функции?

Question

2 ^ n + 6n ^ 2 + 3n

Я полагаю, что это просто O (2 ^ n), используя член высшего порядка, но каков формальный подход к доказательству этого?

Answer 1

Вы можете доказать, что 2 ^ n + n ^ 2 + n = O (2 ^ n) , используя пределы на бесконечности. В частности, f (n) равно O (g (n)) , если lim (n- > inf.) F (n) / g (n) конечно.

lim (n->inf.) ((2^n + n^2 + n) / 2^n)

Поскольку у вас есть inf / inf, неопределенная форма , вы можете использовать правило L'Hopital и различайте числитель и знаменатель, пока не получите что-то Вы можете работать с:

lim (n->inf.) ((ln(2)*2^n + 2n + 1) / (ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*2^n + 2) / (ln(2)*ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*ln(2)*2^n) / (ln(2)*ln(2)*ln(2)*2^n))

Ограничение равно 1, поэтому 2 ^ n + n ^ 2 + n действительно O (2 ^ n) .

Answer 2

Пожалуйста, смотрите:

Домашняя работа с обозначением Big O - анализ алгоритма фрагмента кода?

Big O, как вы рассчитываете / приближаете его?

Can Кто-нибудь, пожалуйста, объясните разницу между нотацией Big-O и Little-O?

Big-O для восьмилетних? (не должно быть оскорбительные)