Questão de complexidade de algoritmos

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:  n²⁰,  n log n, 1, n!, e 2ⁿ. 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: 100²⁰, 100 log 100, 1 (constante), 100! e 2¹⁰⁰. Ordenando os valores resultantes dessas operações, temos:

1 < 100 log 100 < 100²⁰ < 2¹⁰⁰< 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: leonardolima@estrategiaconcursos.com.br

 

abração

 

Leonardo Lima