Lista de exercícios de Algoritmos e complexidade com respostas

Qual notação descreve um limite inferior de crescimento?

1. AΩ (Ômega grande)
2. BΘ (Theta grande)
3. CO (O grande)
4. Do (o pequeno)

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

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

Acessar um elemento de um array pelo índice leva:

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

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

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

Qual é a complexidade de tempo de: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Você ordena um array de n elementos uma vez e depois responde a k consultas de pertinência com busca binária. Qual é o custo total?

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

Qual algoritmo encontra uma árvore geradora mínima adicionando repetidamente a aresta mais barata que não forma um ciclo?

1. AAlgoritmo de Dijkstra
2. BFloyd-Warshall
3. CAlgoritmo de Prim a partir de um nó
4. DAlgoritmo de Kruskal

O que decorreria se alguém encontrasse um algoritmo de tempo polinomial para um problema NP-completo?

1. ATodos os algoritmos de tempo exponencial passariam imediatamente a rodar em tempo linear
2. BSó aquele problema passaria para P
3. CTodo problema em NP poderia ser resolvido em tempo polinomial, então P = NP
4. DO problema da parada se tornaria decidível