Question

Analise o custo computacional dos algoritmos a seguir, que calculam o valor de um polinômio de grau n, daforma: P —— a xn + a xn 1 + ... + a x + aí, onde os coeficientes são números de ponto flutuante armazenadosn n 1 lno vetor a[0..n), e o valor de n é maior que zero. Todos os coeficientes podem assumir qualquer valor, excetoo coeficiente a, que é diferente de zero.Algoritmo 1:soma = a[0]Repita para i = 1 até nSe a[i] 0.0 então potência = xRepita para j = 2 até i potência = potência * xFim repitasoma = soma + a[i] * potencia Fim seFim repita Imprima(soma)Algoritmo 2:soma = a[n]Repita para i = n-1 até 0 passo -1 soma = soma * x + a[i]Fim repita Imprima(soma)Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta entre elas.1. Os algoritmos possuem a mesma complexidade assintótica.PORQUEII. Para o melhor caso, ambos os algoritmos possuem complexidade O(n).A respeito dessas asserções, assinale a opção correta.@‘ As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.@ As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. O asserção I é uma proposição verdadeira, e a II é uma proposição falsa.@ A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. O As asserções I e II são proposições falsas.

#ENADE

Answer 1

A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. Letra D.

É preciso considerar que o algoritmo 2 é a regra de Horner, que apresenta complexidade 0(n) em qualquer caso. Em que o melhor caso do algoritmo 1 acontece quando todos os coeficientes, exceto na, são iguais a zero.

De forma que teremos n comparações a[i] diferente a 0.0. Quando i = n, os comandos do bloco serão finalmente executados. Portanto, a afirmação II é verdadeira. O pior caso do algoritmo 1 acontece quando não ocorre coeficientes iguais a zero.

Bons estudos!

Answer 2

Resposta:

A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.

Explicação: