Lista de exercícios de Algoritmos e complexidade com respostas

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

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

O que significa uma operação rodar em tempo O(1)?

1. ASeu tempo de execução não cresce com o tamanho da entrada
2. BSempre leva exatamente um segundo
3. CSó pode ser executada uma vez
4. DProcessa exatamente um elemento por segundo de tempo de execução

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

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

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

1. AO(n³)
2. BO(n²)
3. CO(n)
4. DO(n 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. ABusca em profundidade (DFS)
2. BAlgoritmo de Dijkstra
3. CAlgoritmo de Kruskal
4. DBellman-Ford é necessário em todos os casos

Qual é a complexidade de tempo do algoritmo padrão de programação dinâmica para a maior subsequência comum de strings de comprimentos m e n?

1. AO(m + n)
2. BO(2^m+n)
3. CO(mn log n)
4. DO(mn)

Como n! e 2ⁿ se comparam para n grande?

1. A2ⁿ cresce mais rápido que n!
2. BCrescem no mesmo ritmo
3. Cn! é O(n²)
4. Dn! cresce mais rápido que 2ⁿ

Usando o teorema mestre, T(n) = 8T(n/2) + O(n²) tem como solução:

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(n³)