Lista de exercícios de Algoritmos e complexidade com respostas

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

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

O que é memoização?

1. ALiberar memória depois que uma função retorna
2. BConverter automaticamente a recursão em um laço equivalente, de modo que não seja preciso pilha de chamadas
3. CArmazenar os resultados de chamadas de função para que chamadas repetidas sejam respondidas da memória
4. DEscrever comentários ao lado de cada linha de código

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. B12 segundos
3. C9 segundos
4. D3 segundos

Qual é a complexidade de tempo de calcular o n-ésimo número de Fibonacci com uma tabela bottom-up?

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

Uma função executa um laço de n iterações e depois, separadamente, outro laço de n iterações. Qual é a sua complexidade de tempo?

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

Qual afirmação sobre uma função recursiva sem caso base alcançável está correta?

1. AEla roda em tempo O(1)
2. BEla retorna 0 automaticamente
3. CO compilador sempre a transforma em um laço que termina com segurança
4. DEla continua chamando a si mesma até a pilha de chamadas estourar

O que o teorema de Cook–Levin estabeleceu?

1. AO problema da parada é indecidível
2. BO problema da satisfatibilidade booleana (SAT) é NP-completo
3. CTodo problema NP pode ser resolvido em tempo exponencial
4. DP é diferente de NP

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

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