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 rápido que g
4. Df cresce estritamente mais devagar que g

Um laço começa com i = 1 e dobra i a cada iteração até i > n. Quantas iterações ele executa?

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

Acessar um elemento de um array pelo índice leva:

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

Qual algoritmo encontra os caminhos mínimos a partir de uma origem em um grafo com pesos de arestas não negativos?

1. AAlgoritmo de Dijkstra
2. BAlgoritmo de Kruskal
3. CBusca em profundidade (DFS)
4. DBellman-Ford é necessário em todos os casos

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²)

A programação dinâmica é útil quando um problema tem:

1. AApenas entradas aleatórias
2. BUm único laço
3. CNenhum subproblema, de modo que pode ser resolvido em um único passo
4. DSubproblemas sobrepostos e subestrutura ótima

Quais duas coisas precisam ser mostradas para provar que um problema de decisão X é NP-completo?

1. AX está em NP, e um problema NP-completo conhecido se reduz a X em tempo polinomial
2. BX está em P, e X se reduz ao SAT
3. CX não tem algoritmo polinomial, e X é decidível
4. DX se reduz a um problema em P, e X está em NP

Qual definição da classe P está correta?

1. AProblemas que exigem tempo exponencial em qualquer computador
2. BProblemas de decisão solúveis por um algoritmo determinístico em tempo polinomial
3. CProblemas cujas soluções podem ser verificadas, mas nunca encontradas, em tempo polinomial
4. DProblemas que podem ser resolvidos em paralelo