Lista de exercícios de Algoritmos e complexidade com respostas

Acessar um elemento de um array pelo índice leva:

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

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

1. A3 segundos
2. B9 segundos
3. C6 segundos
4. D12 segundos

Quanto é log₂ 1024?

1. A12
2. B512
3. C32
4. D10

Com moedas de 1, 3 e 4 e um valor de 6, quantas moedas o método guloso "maior moeda primeiro" usa, em comparação com o ótimo?

1. AO guloso usa 3 moedas; o ótimo é 3
2. BO guloso usa 2 moedas; o ótimo é 2
3. CO guloso usa 4 moedas; o ótimo é 3
4. DO guloso usa 3 moedas; o ótimo é 2

Quantos níveis tem a recursão do merge sort para um array de n elementos?

1. ACerca de n / 2
2. BCerca de n
3. CCerca de log₂ n
4. DCerca de √n

Por que a base do logaritmo costuma ser omitida no O grande, como em O(log n)?

1. ALogaritmos de bases diferentes diferem apenas por um fator constante
2. BOs logaritmos são sempre arredondados para inteiros
3. CTodos os logaritmos em computação têm base 10, então ela fica implícita
4. DA base só importa para n pequeno

O que o teorema de Cook–Levin estabeleceu?

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

O algoritmo de Strassen multiplica matrizes usando 7, em vez de 8, multiplicações recursivas de blocos de metade do tamanho. Qual é o seu tempo de execução?

1. AΘ(n²)
2. BΘ(n³)
3. CΘ(n² log n)
4. DΘ(n^{log₂ 7}), cerca de n^2,81