Lista de exercícios de Algoritmos e complexidade com respostas

Qual é a complexidade de tempo da busca linear em um array não ordenado com n elementos (pior caso)?

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

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

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

Qual destas cresce mais devagar quando n fica grande?

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

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

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

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

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

A busca em largura (BFS) em um grafo não ponderado encontra:

1. AA árvore geradora mínima
2. BUma ordenação topológica em todos os grafos
3. CCaminhos mínimos em grafos que contêm arestas com pesos negativos
4. DCaminhos mínimos em número de arestas a partir do nó inicial

O insertion sort roda em O(n) com entrada ordenada. Isso contradiz o limite inferior Ω(n log n) da ordenação por comparação?

1. ASim, mas só para arrays com menos de 100 elementos
2. BNão, o limite inferior vale para o pior caso entre todas as entradas, não para cada entrada
3. CSim, portanto o limite inferior está errado
4. DNão, porque o insertion sort não é uma ordenação por comparação

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

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