Lista de exercícios de Algoritmos e complexidade com respostas

Qual é a complexidade de tempo da busca em profundidade num grafo armazenado como listas de adjacência?

1. AO(V²)
2. BO(E log V)
3. CO(V × E)
4. DO(V + E)

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. B9 segundos
3. C12 segundos
4. D3 segundos

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

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

O que a análise amortizada mede?

1. AO custo de um algoritmo com a melhor entrada
2. BO custo médio por operação ao longo de uma sequência de operações de pior caso
3. CO custo da operação individual mais cara em qualquer ponto da sequência
4. DO custo esperado sobre entradas aleatórias

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

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

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

Qual destes problemas de satisfatibilidade é sabidamente solúvel em tempo polinomial?

1. A2-SAT, em que cada cláusula tem no máximo dois literais
2. BSatisfatibilidade de circuitos
3. C3-SAT, em que cada cláusula tem exatamente três literais
4. DSAT geral em fórmulas na forma normal conjuntiva

Qual técnica dá ao quicksort um tempo de execução esperado O(n log n) para qualquer entrada?

1. ASempre escolher o primeiro elemento
2. BOrdenar a entrada antes de executar o quicksort
3. CEscolher o pivô de forma uniformemente aleatória
4. DUsar recursão apenas no lado esquerdo