Lista de exercícios de Algoritmos e complexidade com respostas

O que significa f(n) = Θ(g(n))?

1. Af é sempre menor que g para todo n, então g a limita por cima, mas nunca por baixo
2. Bf cresce no mesmo ritmo que g, limitada por cima e por baixo por múltiplos constantes de g
3. Cf cresce estritamente mais devagar que g
4. Df cresce estritamente mais rápido que g

Qual classe de complexidade cresce mais rápido para n grande?

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

O que a busca binária exige da sua entrada?

1. AO array deve estar ordenado
2. BO tamanho do array deve ser uma potência de dois
3. CO array deve conter só números positivos
4. DO array não pode ter mais de 1000 elementos

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

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

Aproximadamente quantas comparações a busca binária precisa no pior caso num array ordenado de 1,000,000 de elementos?

1. ACerca de 1,000
2. BCerca de 20
3. CCerca de 500,000
4. DCerca de 100

Como o algoritmo de Bellman–Ford detecta um ciclo de peso negativo alcançável a partir da origem?

1. AApós V − 1 rodadas, verifica se alguma aresta ainda pode ser relaxada
2. BConta os ciclos com busca em profundidade
3. CVerifica se alguma aresta tem peso negativo
4. DExecuta o algoritmo de Dijkstra duas vezes e compara os dois resultados de distância

Qual afirmação sobre a notação o pequeno está correta?

1. An = o(n²), mas n não é o(n)
2. Bn² = o(n)
3. Cn = o(n), já que toda função é o pequeno de si mesma
4. D2n = o(n), porque 2n cresce devagar