Lista de exercícios de Algoritmos e complexidade com respostas

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

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

Um laço começa com i = 1 e dobra i a cada iteração até i > n. Quantas iterações ele executa?

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

Qual estratégia de projeto o merge sort usa?

1. AForça bruta
2. BEscolha gulosa
3. CDivisão e conquista
4. DProgramação dinâmica

Qual é o tempo de execução do radix sort LSD para n inteiros com d dígitos na base k?

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

Por que a programação dinâmica não traz ganho real de velocidade para o merge sort?

1. AA programação dinâmica só funciona em problemas de grafos, não em vetores
2. BSeus subproblemas não se sobrepõem, então não há nada para reaproveitar
3. CO merge sort já é O(n)
4. DO merge sort não tem estrutura recursiva

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. BRemove a aresta mais cara até não restarem ciclos
3. COrdena todas as arestas por peso e adiciona cada uma, a menos que forme um ciclo na floresta
4. DFaz crescer uma árvore a partir de um vértice inicial, adicionando a aresta mais barata que sai da árvore

Como é classificado o problema do caixeiro-viajante?

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

Por que qualquer busca baseada em comparações num array ordenado precisa de Ω(log n) comparações no pior caso?

1. AUma árvore de decisão com n resultados possíveis precisa ter profundidade de pelo menos log₂ n
2. BA busca binária é o único algoritmo possível e precisa de log₂ n comparações
3. CCada comparação leva tempo logarítmico
4. DTodo elemento precisa ser comparado pelo menos uma vez