Numero:
Uma empresa de telefonia recebeu reclamações sobre má qualidade do sinal ou ausência do mesmo. Ao analisar a distribuição de suas torres e a cobertura das mesmas, foi observado a má distribuição das torres.
Em duas regiões a e b, hora as torres se sobrepunham a cobertura, hora elas não cobriam uma certa área.
Sendo os pontos em negritos a posição da torre, dado por tn(x,y), e a área sombreada a cobertura total das mesmas.Dada uma função f(tn) que retorna um índice de cobertura da torre, essa empresa resolveu o problema através da disposição de pares de torres, cujos índices fossem os k-ésimos maiores e menores respectivamente do conjunto de torres. O que é correto afirmar sobre um melhor algoritmo, em custos temporal e de comparação, que retornaria simultaneamente o maior e menor elemento de um vetor, de tamanho n dos índices de cobertura.
a. Esse algoritmo teria como caso médio O(n) e pior caso O(n²)
b.Seria necessária uma ordenação por comparação, logo é certo que o melhor caso nunca seria menor que Θ(nlogn)
c. O algoritmo:
for 1 to n do { if (menor(i) { menor =i} if(maior(i) {maior=i} }
É o mais eficiente em custos temporal e de comparação.
d. É possível realizar em média menos que duas comparações por elemento desse vetor para obtermos os elementos cujo índice seja o maior e menor respectivamente.
e. N.D.A
Ideia original de: Otávio Augusto Araújo Silva
Nenhum comentário:
Postar um comentário