Lista de exercícios de Algoritmos e complexidade com respostas

Qual é o O grande de 3n² + 5n + 2?

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

O que é um algoritmo de força bruta?

1. AUm que roda em vários processadores
2. BUm que sempre usa recursão
3. CUm que testa todas as soluções candidatas possíveis
4. DUm que chuta uma resposta ao acaso

O que é recursão?

1. AUm laço que nunca termina
2. BUm tipo de estrutura de dados
3. CUma função que chama a si mesma com entradas menores
4. DUm método de ordenação

Como o algoritmo de Prim constrói uma árvore geradora mínima?

1. AExecuta uma busca em largura e mantém a árvore da BFS
2. BFaz crescer uma árvore a partir de um vértice inicial, adicionando a aresta mais barata que sai da árvore
3. COrdena todas as arestas por peso e adiciona cada uma, a menos que forme um ciclo na floresta
4. DRemove a aresta mais cara até não restarem ciclos

Um algoritmo guloso (greedy):

1. ATesta todas as soluções possíveis
2. BFaz a melhor escolha local em cada passo
3. CSempre fornece a solução ótima
4. DUsa apenas recursão

Qual algoritmo de ordenação é estável?

1. ASelection sort (versão típica)
2. BMerge sort
3. CHeap sort
4. DQuicksort (versão in-place típica)

Quais são os custos de tempo e espaço de calcular o n-ésimo número de Fibonacci com um laço que guarda só os dois últimos valores?

1. ATempo O(n) e espaço O(n)
2. BTempo O(log n) e espaço O(n)
3. CTempo O(n) e espaço O(1)
4. DTempo O(2ⁿ) e espaço O(1)

A multiplicação de Karatsuba satisfaz T(n) = 3T(n/2) + O(n). Qual é a solução?

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n^{log₂ 3}), cerca de n^1,585
4. DΘ(n³)