O que é o método adequado para ir sobre encontrar a ordem de crescimento para esta função?
-
06-07-2019 - |
Pergunta
2 ^ n + 6n + 2 ^ 3n
Eu acho que é apenas O (2 ^ n), usando o termo de ordem mais alta, mas o que é a abordagem formal para ir para provar isso?
Solução
Você pode provar que 2^n + n^2 + n = O(2^n)
usando limites no infinito. Especificamente, f(n)
é O(g(n))
se lim (n->inf.) f(n)/g(n)
é finito.
lim (n->inf.) ((2^n + n^2 + n) / 2^n)
Uma vez que você tem inf / inf, um indeterminado forma , você pode usar regra de L'Hopital e diferenciar o numerador eo denominador até conseguir algo você pode trabalhar com:
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))
O limite é 1, então 2^n + n^2 + n
é realmente O(2^n)
.
Outras dicas
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow