Lista de exercícios de Algoritmos e complexidade com respostas

Como se chama o crescimento O(2ⁿ)?

1. ALogarítmico
2. BLinear
3. CPolinomial
4. DExponencial

O que é o caso base de uma função recursiva?

1. AA chamada que usa mais memória
2. BUm caso respondido diretamente, sem fazer outra chamada recursiva
3. CA primeira linha da função
4. DO caso com a maior entrada, que é tratado antes de quaisquer chamadas recursivas

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

1. A9 segundos
2. B6 segundos
3. C3 segundos
4. D12 segundos

O que o algoritmo de Floyd–Warshall calcula, e com que rapidez?

1. ACaminhos mínimos de um vértice de origem para todos os outros em O(V + E)
2. BCaminhos mínimos entre todos os pares de vértices em O(V³)
3. CUma ordenação topológica em O(V²)
4. DUma árvore geradora mínima em O(E log V)

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 é 2
2. BO guloso usa 4 moedas; o ótimo é 3
3. CO guloso usa 2 moedas; o ótimo é 2
4. DO guloso usa 3 moedas; o ótimo é 3

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

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

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

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

Qual é a complexidade de tempo de: for i = 1 to n: for (j = i; j ≤ n; j = j + i) faça trabalho O(1)?

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