Lista de exercícios de Algoritmos e complexidade com respostas

Qual estratégia de projeto o merge sort usa?

1. AEscolha gulosa
2. BDivisão e conquista
3. CForça bruta
4. DProgramação dinâmica

Um algoritmo O(n²) leva 1 segundo para n = 1000. Quanto tempo leva, aproximadamente, para n = 2000?

1. A8 segundos
2. B4 segundos
3. C1 segundo
4. D2 segundos

O que é memoização?

1. AEscrever comentários ao lado de cada linha de código
2. BConverter automaticamente a recursão em um laço equivalente, de modo que não seja preciso pilha de chamadas
3. CLiberar memória depois que uma função retorna
4. DArmazenar os resultados de chamadas de função para que chamadas repetidas sejam respondidas da memória

O limite inferior para ordenação baseada em comparações no pior caso é:

1. AΩ(n²)
2. BΩ(log n)
3. CΩ(n log n)
4. DΩ(n)

Qual é a complexidade de tempo do algoritmo padrão de programação dinâmica para a maior subsequência comum de strings de comprimentos m e n?

1. AO(2^m+n)
2. BO(mn)
3. CO(mn log n)
4. DO(m + n)

Qual é a solução da recorrência T(n) = T(n/2) + O(1)?

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

Qual definição da classe NP está correta?

1. AProblemas que não são polinomiais
2. BProblemas que não podem ser resolvidos em tempo polinomial
3. CProblemas que nenhum algoritmo consegue resolver
4. DProblemas de decisão cujas respostas "sim" podem ser verificadas em tempo polinomial dado um certificado

Qual afirmação sobre selecionar o k-ésimo menor elemento de um array não ordenado está correta?

1. AO quickselect roda em O(n) esperado, e a mediana das medianas garante O(n) no pior caso
2. BO quickselect roda em O(log n) no pior caso, porque faz recursão em apenas um lado do pivô
3. CA seleção sempre exige Ω(n log n), porque requer ordenação
4. DA seleção só é possível em O(n²)