Lista de exercícios de Algoritmos e complexidade com respostas

A complexidade de espaço mede:

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

Um algoritmo O(n) leva 3 segundos para n = 1 milhão. Quanto tempo leva, aproximadamente, para n = 2 milhões?

1. A6 segundos
2. B3 segundos
3. C12 segundos
4. D9 segundos

Qual é a complexidade de tempo da busca binária em um array ordenado?

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

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

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

Um algoritmo guloso (greedy):

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

O que a análise amortizada mede?

1. AO custo de um algoritmo com a melhor entrada
2. BO custo médio por operação ao longo de uma sequência de operações de pior caso
3. CO custo da operação individual mais cara em qualquer ponto da sequência
4. DO custo esperado sobre entradas aleatórias

Qual definição da classe P está correta?

1. AProblemas cujas soluções podem ser verificadas, mas nunca encontradas, em tempo polinomial
2. BProblemas que exigem tempo exponencial em qualquer computador
3. CProblemas que podem ser resolvidos em paralelo
4. DProblemas de decisão solúveis por um algoritmo determinístico em tempo polinomial

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

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