Lista de exercícios de Algoritmos e complexidade com respostas

O que é memoização?

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

O que descreve o tempo de execução de um algoritmo no pior caso?

1. AO tempo esperado que leva com uma entrada aleatória de tamanho n
2. BO tempo que leva num computador lento
3. CO tempo que leva com a menor entrada
4. DO tempo máximo que ele leva entre todas as entradas de tamanho n

Acessar um elemento de um array pelo índice leva:

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

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

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

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

Qual é a complexidade de tempo amortizada de adicionar ao final de um array dinâmico que dobra sua capacidade quando fica cheio?

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

Qual é a solução da recorrência T(n) = 2T(n/2) + n log n?

1. AΘ(n log n)
2. BΘ(n log² n)
3. CΘ(n²)
4. DΘ(n)

Usando o teorema mestre, T(n) = 8T(n/2) + O(n²) tem como solução:

1. AΘ(n log n)
2. BΘ(n²)
3. CΘ(n² log n)
4. DΘ(n³)