Lista de exercícios de Algoritmos e complexidade com respostas

Qual destas cresce mais devagar quando n fica grande?

1. AO(log n)
2. BO(n²)
3. CO(n log n)
4. DO(n)

A complexidade de espaço mede:

1. AO tamanho físico do computador
2. BO espaço em disco do arquivo do programa depois de compilado
3. CA quantidade de memória que um algoritmo precisa à medida que a entrada cresce
4. DO número de linhas de código

Como funciona o selection sort?

1. AInsere cada elemento numa parte ordenada crescente por deslocamento
2. BEncontra repetidamente o mínimo da parte não ordenada e o troca para a frente
3. CTroca repetidamente elementos vizinhos que estão na ordem errada
4. DDivide o array em metades e as intercala

Quantos níveis tem a recursão do merge sort para um array de n elementos?

1. ACerca de n
2. BCerca de √n
3. CCerca de log₂ n
4. DCerca de n / 2

É correto dizer que um algoritmo O(n²) também é O(n³)?

1. ASim, mas só se n for menor que 100
2. BNão, porque n³ é menor que n² para n grande
3. CSim, porque o O grande é um limite superior e n² não cresce mais rápido que n³
4. DNão, porque o O grande deve sempre dar a taxa de crescimento exata da função

Por que a base do logaritmo costuma ser omitida no O grande, como em O(log n)?

1. ALogaritmos de bases diferentes diferem apenas por um fator constante
2. BOs logaritmos são sempre arredondados para inteiros
3. CTodos os logaritmos em computação têm base 10, então ela fica implícita
4. DA base só importa para n pequeno

Como é classificado o problema do caixeiro-viajante?

1. AÉ indecidível
2. BA versão de decisão está em P, mas a versão de otimização é NP-completa
3. CEstá em P, porque o algoritmo de Dijkstra o resolve visitando cada cidade uma única vez
4. DA versão de decisão é NP-completa e a versão de otimização é NP-difícil

O que o teorema de Cook–Levin estabeleceu?

1. AP é diferente de NP
2. BO problema da parada é indecidível
3. CTodo problema NP pode ser resolvido em tempo exponencial
4. DO problema da satisfatibilidade booleana (SAT) é NP-completo