Considere uma função com comportamento assintótico O(n5). Se...

Próximas questões
Com base no mesmo assunto
Q4114041
Algoritmos e Estrutura de Dados Algoritmos , Complexidade de Algoritmos ,
Ano: 2022 Banca: FCM Órgão: IF-BA Prova: FCM - 2022 - IF-BA - Professor PEBTT - Ciência da Computação |
Q4114041 Algoritmos e Estrutura de Dados
Considere uma função com comportamento assintótico O(n5). Se para uma entrada de tamanho 10 o tempo de execução desta função é de 0.1 segundos, para uma entrada de tamanho 40 o tempo de execução será de
Alternativas

Gabarito comentado

Confira o gabarito comentado por um dos nossos professores

Gabarito: C

Fundamento decisivo: O ponto decisivo era aplicar o crescimento de quinta ordem à mudança de tamanho da entrada, usando a razão entre 40 e 10 para chegar ao tempo correspondente e então converter o resultado para a unidade pedida.

Tema central: Escalonamento assintótico
Análise das alternativas
A
Errada
Incorreta. 3,2 segundos é muito inferior ao valor correto de 102,4 segundos, que resulta de 0,1 × (40/10)^5.
B
Errada
Incorreta. 24,3 segundos também não coincide com o escalonamento por n^5, pois o cálculo correto leva a 102,4 segundos.
C
Certa
A alternativa C está correta porque a questão exige comparar dois tamanhos de entrada sob crescimento de quinta ordem. Assumindo a proporcionalidade T(n) = k·n^5, a mudança de n = 10 para n = 40 multiplica o tempo por (40/10)^5 = 1024. Assim, o novo tempo é 0,1 × 1024 = 102,4 segundos, que correspondem a 102,4/60 ≈ 1,7 minuto.
D
Errada
Incorreta. 5,2 minutos equivalem a 312 segundos, valor superior ao tempo obtido pelo critério correto de quinta potência, que é 102,4 segundos.
E
Errada
Incorreta. 13 minutos equivalem a 780 segundos, valor muito acima do que resulta do escalonamento proporcional por n^5.
Pegadinha da questão
Esquecer de elevar a razão 40/10 à quinta potência ou errar a conversão de 102,4 segundos para minutos.
Dica para questões semelhantes
  • Quando a questão pede estimativa entre dois tamanhos e informa crescimento como n^p, compare os tempos pela razão (n2/n1)^p.
  • Se um tempo inicial é dado, multiplique esse tempo pela razão de crescimento antes de escolher a alternativa.
  • Ao final, confronte o resultado com a unidade cobrada na resposta; aqui, era necessário converter segundos em minutos.

Clique para visualizar este gabarito

Visualize o gabarito desta questão clicando no botão abaixo

Questões de assuntos semelhantes

Provas relacionadas