Lista de exercícios de Algoritmos e complexidade com respostas

Quais são as três etapas de um algoritmo de divisão e conquista?

1. AChutar, verificar, repetir
2. BLer, calcular, escrever
3. CDividir, conquistar, combinar
4. DOrdenar, buscar, retornar

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³)

A complexidade de espaço mede:

1. AO espaço em disco do arquivo do programa depois de compilado
2. BO número de linhas de código
3. CO tamanho físico do computador
4. DA quantidade de memória que um algoritmo precisa à medida que a entrada cresce

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 log n + k log n)
3. CO(n + k)
4. DO(k n log n)

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

1. AO(n²)
2. BO(n)
3. CO(2ⁿ)
4. DO(n log 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. BO problema tem exatamente uma solução ótima, compartilhada por todos os subproblemas
3. CTodos os subproblemas têm o mesmo tamanho
4. DO problema pode ser resolvido em tempo constante

O problema da mochila 0/1 resolvido com programação dinâmica leva tempo O(nW). Por que isso é chamado de pseudopolinomial?

1. APorque n é sempre pequeno
2. BPorque o algoritmo é aleatorizado e seu tempo de execução varia a cada entrada
3. CPorque só funciona para W = 0
4. DW é um número, então o tempo é exponencial no número de bits usados para escrever W

2²ⁿ está em O(2ⁿ)?

1. ANão, porque 2²ⁿ cresce mais devagar que 2ⁿ
2. BNão, porque 2²ⁿ = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce sem limite
3. CSim, porque ambos são exponenciais
4. DSim, porque fatores constantes no expoente são sempre ignorados no O grande