Lista de exercícios de Algoritmos e complexidade com respostas

Como se chama o crescimento O(2ⁿ)?

1. AExponencial
2. BPolinomial
3. CLinear
4. DLogarítmico

Quanto é log₂ 1024?

1. A32
2. B10
3. C512
4. D12

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

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

O que significa um problema ter subestrutura ótima?

1. AUma solução ótima pode ser construída a partir de soluções ótimas dos seus subproblemas
2. BTodos os subproblemas têm o mesmo tamanho
3. CO problema pode ser resolvido em tempo constante
4. DO problema tem exatamente uma solução ótima, compartilhada por todos os subproblemas

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(mn log n)
2. BO(mn)
3. CO(2^m+n)
4. DO(m + n)

Você ordena um array de n elementos uma vez e depois responde a k consultas de pertinência com busca binária. Qual é o custo total?

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

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

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

Por que o algoritmo de Dijkstra pode dar resultados errados quando alguns pesos de aresta são negativos?

1. AUm vértice é finalizado ao ser extraído, mas uma aresta negativa posterior ainda poderia dar a ele um caminho mais curto
2. BNúmeros negativos não podem ser armazenados numa fila de prioridade
3. CSó funciona em grafos não dirigidos
4. DEntra num laço infinito a cada aresta negativa