Lista de exercícios de Algoritmos e complexidade com respostas

Qual classe de complexidade cresce mais rápido para n grande?

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

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

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

O que descreve o tempo de execução no caso médio?

1. AO tempo no computador mais comum
2. BO tempo esperado sobre uma dada distribuição de entradas de tamanho n
3. CO tempo para uma entrada de comprimento médio
4. DO valor intermediário entre os tempos de execução do melhor e do pior caso

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

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

No problema de seleção de atividades, qual regra gulosa sempre dá o número máximo de atividades sem sobreposição?

1. AEscolher primeiro a atividade mais curta
2. BEscolher a atividade que começa mais cedo
3. CEscolher a atividade que termina mais cedo e repetir com as compatíveis
4. DEscolher primeiro a atividade com menos sobreposições e repetir com as compatíveis

A busca em largura (BFS) em um grafo não ponderado encontra:

1. ACaminhos mínimos em número de arestas a partir do nó inicial
2. BA árvore geradora mínima
3. CCaminhos mínimos em grafos que contêm arestas com pesos negativos
4. DUma ordenação topológica em todos os grafos

Como n! e 2ⁿ se comparam para n grande?

1. A2ⁿ cresce mais rápido que n!
2. Bn! cresce mais rápido que 2ⁿ
3. CCrescem no mesmo ritmo
4. Dn! é O(n²)

Um problema é NP-completo se ele:

1. APode ser resolvido em tempo polinomial
2. BÉ impossível de resolver
3. CEstá em NP e todo problema NP se reduz a ele em tempo polinomial
4. DEstá fora de NP, mas é mais difícil que todos os problemas NP, como o problema da parada