Ola meus amigos concurseiros de TI, vamos fechar a semana com uma “leve” questão de complexidade de algoritmos ????
Analista Judiciário – TRT 8ª Região 2010 – FCC
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.
|
Time |
Complexidade |
|
Branco |
O (n20) |
|
Amarelo |
O (n log n) |
|
Azul |
O (1) |
|
Verde |
O (n!) |
|
Vermelho |
O (2n) |
O time que obteve a medalha de prata (2º algoritmo mais eficiente) é o
a) Branco.
b) Amarelo.
c) Azul.
d) Verde.
e) Vermelho.
Para quem não lembra ou nunca viu a notação Big O, também conhecida como notação assintótica, ela é usada para descrever a função de complexidade de um algoritmo. Então, quanto mais complexo o algoritmo (em termos de ciclo de repetições), maior a magnitude de sua função assintótica. O que isso quer dizer na prática?
Vamos analisar as funções da questão: n20, n log n, 1, n!, e 2n. De maneira simplificada, n é o tamanho da entrada. Se trocarmos n por um número inteiro, tipo 100, podemos ter uma ideia da magnitude de cada função: 10020, 100 log 100, 1 (constante), 100! e 2100. Ordenando os valores resultantes dessas operações, temos:
1 < 100 log 100 < 10020 < 2100< 100!.
A questão pede o 2º algoritmo mais eficiente. Logo, é o algoritmo do time amarelo, com complexidade O (n log n). Letra B.
Gostaram? Dúvidas e dívidas, mandem um e-mail: [email protected]
abração
Leonardo Lima