Numa competição de programação, ganhava mais pontos o time q...
Próximas questões
Com base no mesmo assunto
Ano: 2010
Banca:
FCC
Órgão:
TRT - 8ª Região (PA e AP)
Prova:
FCC - 2010 - TRT - 8ª Região (PA e AP) - Analista Judiciário - Tecnologia da Informação |
Q80233
Algoritmos e Estrutura de Dados
Numa competição de programação, ganhava mais pontos o time que apresentasse o algoritmo mais eficiente para resolver o pior caso de um determinado problema. A complexidade assintótica (notação Big O) dos algoritmos elaborados está ilustrada na tabela abaixo.
O time que obteve a medalha de prata (2o algoritmo mais eficiente) é o
O time que obteve a medalha de prata (2o algoritmo mais eficiente) é o
Comentários
Veja os comentários dos nossos alunos
O mais eficiente seria o O(1)
Depois o O(n log n)
Depois o O(n!)
Fico em dúvida em qual dos outros dois vem primeiro, acho que é assim a odem:
Depois o O(2^n)
Depois o O(n^20)
Depois o O(n log n)
Depois o O(n!)
Fico em dúvida em qual dos outros dois vem primeiro, acho que é assim a odem:
Depois o O(2^n)
Depois o O(n^20)
6. Classes de comportamento assintótico
f (n) = O(1) (complexidade constante)
O uso do algoritmo independe do tamanho de n. Neste caso as instruções
do algoritmo são executadas um número fixo de vezes.
f(n)= O(n) (complexidade de linear)
Em geral um pequeno trabalho é realizado sobre cada elemento de entrada.
Esta é a melhor situação possível para um algoritmo que tem que processar
n elementos de entrada ou produzir n elementos de saída. Cada vez que n
dobra de tamanho o tempo de execução dobra.
f(n) = O(log n) (complexidade logarítmica)
Ocorre tipicamente em algoritmos que resolvem um problema
transformando-o em problemas menores. Nestes casos, o tempo de
execução pode ser considerado como sendo menor do que uma constante
grande. Por exemplo, quando n é um milhão, log2 n é aprox. 20.
f(n)= O(nlogn)
Este tempo de execução ocorre tipicamente em algoritmos que resolvem um
problema quebrando-o em problemas menores, resolvendo cada um deles
independentemente e depois ajuntando as soluções. Por exemplo, quando n
é um milhão e a base do logaritmo é 2, nlog2 n é cerca de 20 milhões.
f(n)= O(n^2) (complexidade quadrática)
Algoritmos desta ordem de complexidade ocorrem quando os itens de
dados são processados aos pares, muitas vezes em um anel dentro de
outro. Por exemplo, quando n é mil, o número de operações é da ordem
de 1 milhão. Algoritmos deste tipo somente são úteis para resolver
problemas de tamanhos relativamente pequenos.
f(n)= O(2^n) (complexidade exponencial)
Algoritmos desta ordem de complexidade geralmente não são úteis sob o
ponto de vista prático. Eles ocorrem na solução de problemas quando se
usa força bruta para resolvê-los. Por exemplo, quando n é vinte, o tempo
de execução é cerca de um milhão. Problemas que somente podem ser
resolvidos através de algoritmos exponenciais são ditos intratáveis.
(Fonte: http://www.deinf.ufma.br/~acmo/grad/ED_complexidade_2005.pdf)
(Fonte: http://www.deinf.ufma.br/~acmo/grad/ED_complexidade_2005.pdf)
Complementando, n! cresce ainda mais rápido que a exponencial (basta plotar um gráfico para constatar).
A ordem das equipes, portanto, seria: Azul (O(1)), Amarelo (O(nlogn), Branco (O(n^20)), Vermelho (O(2^n)) e Verde (O(n!)).
A ordem das equipes, portanto, seria: Azul (O(1)), Amarelo (O(nlogn), Branco (O(n^20)), Vermelho (O(2^n)) e Verde (O(n!)).
Em ordem:
1) O (1)
2) O (log n)
3) O (n)
4) O (n log n)
5) O (n^2)
6) O (2^n)
7) O (n!)
Clique para visualizar este comentário
Visualize os comentários desta questão clicando no botão abaixo
Conheça nossos planos