Um programador deve propor um algoritmo para determinar oresultado de uma eleição. Sabe-se que o número n de eleitores é tão grande que o armazenamento do vetor de eleitoresem memória, ou em arquivo, torna-se inviável. O número decandidatos, no pior caso, pode ser igual ao de eleitores. Alémdisso, as cédulas de eleição podem ser reinseridas no sistema de contagem tantas vezes quantas forem necessárias.Nesta eleição, o candidato somente será eleito por maioriaabsoluta e cada eleitor votará uma única vez. Caso não exista um candidato eleito, a eleição será anulada. Apenas duasvariáveis inteiras devem ser utilizadas no algoritmo para determinar o resultado da eleição: uma para armazenamento donúmero do candidato vitorioso e a outra, a critério do programador. O algoritmo ótimo para a solução deste problema temcomplexidade(A) O(1)(B) O(log n)(C) O(n)(D) O(n log n)(E) O(n^2)
#ENADE
Soluções para a tarefa
O algoritmo ótimo para a solução deste problema tem complexidade igual a: Alternativa C) O(n).
Vamos a lembrar que,a complexidade de um algoritmo refere-se à quantidade de trabalho necessária para realizar sua execução, em função das operações fundamentais, e isso segundo o algoritmo e o volume de dados.
I) Incorreta: A função f(n)=O(1) é para algoritmos de complexidade constante, nos quais o uso do algoritmo independe do tamanho de n.
II) Incorreta: A função f(n)= O(logn) refere-se a algoritmos de complexidade logarítmica.
III) Correta: A função f(n)=O(n) é para algoritmos de complexidade linear, onde, os elementos de entrada recebem um tipo de tratamento. É a melhor opção para um algoritmo que deve processar n elementos de entrada (número de votos) ou produzir n elementos de saída (número de candidatos eleitos).
IV) Incorreta: A função f(n)=O(nlogn) é para algoritmos que dividem o problema em problemas menores.
V) Incorreta: A função f(n)=O(n²) refere-se a algoritmos de complexidade quadrática.
Resposta:
Letra C O(n)
Explicação:
DNM