Lista de exercícios de Algoritmos e complexidade com respostas

Um problema costuma ser chamado de tratável se:

1. APode ser resolvido em tempo polinomial
2. BPode ser resolvido em tempo constante
3. CNão tem solução
4. DSó pode ser resolvido testando todas as possibilidades

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. C12 segundos
4. D6 segundos

Quanto é log₂ 1024?

1. A512
2. B12
3. C10
4. D32

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

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

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

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

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

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

Caminhos simples mínimos podem ser encontrados em tempo polinomial. O que se sabe sobre encontrar o caminho simples mais longo entre dois vértices num grafo geral?

1. AÉ NP-difícil
2. BÉ sempre solúvel em O(V + E)
3. CPode ser resolvido pelo algoritmo de Dijkstra com os pesos negados
4. DÉ indecidível

Qual é a complexidade de tempo para construir um heap binário a partir de n elementos não ordenados com o método bottom-up?

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