Dois algoritmos A e B possuem complexidade
e
respectivamente. Você utilizaria o algoritmo B ao invés do A , em qual caso? Explique.
Passo 1
Temos dois algoritmos: A de complexidade
e B de complexidade
. O conteúdo aqui é análise assintótica de algoritmos, e vamos precisar comparar o crescimento de uma função polinomial com o de uma função exponencial para decidir qual algoritmo é melhor em cada caso.
Passo 2
Em geral funções exponenciais crescem muito mais rápido que polinomiais quando
aumenta. Para decidir quando usar B, precisamos achar para quais valores de
vale
Para isso, podemos testar alguns valores inteiros de
A partir de
Passo 3
Portanto, o algoritmo B (exponencial) só é mais rápido que A (polinomial) quando o tamanho do problema é pequeno o suficiente para satisfazer
, ou seja, para
aproximadamente até 24.
Resposta
Usar o algoritmo B apenas para valores de n pequenos (aproximadamente n ≤ 24), pois além disso a complexidade exponencial se torna maior que a polinomial de grau 5.