Lista de exercícios de Algoritmos e complexidade com respostas

Um algoritmo com dois laços aninhados, cada um executado n vezes, normalmente tem qual complexidade?

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

Qual é o tempo de execução do counting sort para n inteiros no intervalo de 0 a k?

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

Como funciona o selection sort?

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

Qual afirmação sobre uma função recursiva sem caso base alcançável está correta?

1. AO compilador sempre a transforma em um laço que termina com segurança
2. BEla retorna 0 automaticamente
3. CEla roda em tempo O(1)
4. DEla continua chamando a si mesma até a pilha de chamadas estourar

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

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

A recorrência T(n) = 2T(n/2) + O(n) tem como solução:

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

Qual é a diferença entre um problema indecidível e um intratável?

1. AProblemas indecidíveis estão em NP, enquanto os intratáveis estão em P
2. BProblemas intratáveis não podem ser resolvidos por nenhum algoritmo, enquanto os indecidíveis só exigem tempo exponencial
3. CNenhum algoritmo resolve um problema indecidível para todas as entradas, enquanto um intratável tem algoritmo, mas é lento demais
4. DAmbos significam que o problema não tem nenhum algoritmo

Tomar as duas extremidades de cada aresta de um emparelhamento maximal dá uma cobertura de vértices. Quão boa é essa cobertura?

1. ANo máximo o dobro do tamanho de uma cobertura de vértices mínima
2. BDe qualidade desconhecida em relação ao ótimo
3. CSempre uma cobertura de vértices mínima
4. DNo máximo log n vezes o mínimo