Dois algoritmos A e B possuem complexidade n^5 e 2^n respectivamente. Você utilizaria o algoritmo B ao invés do A , em qual caso? Explique.

Passo 1

Temos dois algoritmos: A de complexidade n^5 e B de complexidade 2^n. 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 n aumenta. Para decidir quando usar B, precisamos achar para quais valores de n vale
2^n < n^5
Para isso, podemos testar alguns valores inteiros de n:
n=10:;2^10=1024,;10^5=100000 ( 2^10<10^5)
n=20:;2^20=1,048,576,;20^5=3,200,000 (ainda 2^20<20^5)
n=25:;2^25approx33,554,432,;25^5=9,765,625 (agora 2^25>25^5).
A partir de n=25 em diante, 2^n ultrapassa n^5.

Passo 3

Portanto, o algoritmo B (exponencial) só é mais rápido que A (polinomial) quando o tamanho do problema é pequeno o suficiente para satisfazer 2^n, ou seja, para n 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.

Exercícios relacionados