Question

2 ^ n + 6n ^ 2 + 3n

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

bobbymcr · Answer 1 · 13 сентября 2009

Вы можете доказать это 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, неопределенная форма , вы можете использовать правило Л'Опитала и различать числитель и знаменатель, пока не получите что-то, с чем вы можете работать:

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).