Complexidade big-o de c^n + n*(logn)^2 + (10*n)^c
-
25-09-2019 - |
Pergunta
Eu preciso derivar a complexidade grande dessa expressão:
c^n + n*(log (n))^2 + (10*n)^c
onde C é uma constante e n é uma variável.
Tenho certeza de que entendo como derivar a complexidade Big-O de cada termo individualmente, simplesmente não sei como a complexidade Big-O muda quando os termos são combinados assim.
Ideias?
Qualquer ajuda seria ótima, obrigado.
Solução
A notação o () considera o termo mais alto; pense em qual deles dominará para valores muito, muito grandes de n
.
No seu caso, o termo mais alto é c^n
, na realidade; Os outros são essencialmente polinomiais. Então, é complexidade exponencial.
Outras dicas
A resposta depende de | C |
Se | C | <= 1 é o (n*(log (n))^2)
Se | C | > 1 é o (c^n)
No uso típico, a definição formal de notação O não é usada diretamente; Em vez disso, a notação O para uma função f (x) é derivada pelas seguintes regras de simplificação:
- Se f (x) é uma soma de vários termos, a maior taxa de crescimento é mantida e todos os outros omitidos.
- Se f (x) é um produto de vários fatores, quaisquer constantes (termos no produto que não dependem de x) serão omitidos.