Lista de exercícios de Algoritmos e complexidade com respostas

Qual é o tempo de execução do counting sort para n inteiros no intervalo de 0 a k?

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

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

1. Ao (o pequeno)
2. BO (O grande)
3. CΩ (Ômega grande)
4. DΘ (Theta grande)

Como funciona o selection sort?

1. ATroca repetidamente elementos vizinhos que estão na ordem errada
2. BInsere cada elemento numa parte ordenada crescente por deslocamento
3. CDivide o array em metades e as intercala
4. DEncontra repetidamente o mínimo da parte não ordenada e o troca para a frente

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

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

Qual algoritmo de ordenação é estável?

1. ASelection sort (versão típica)
2. BHeap sort
3. CQuicksort (versão in-place típica)
4. DMerge sort

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

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

Por que o algoritmo de Dijkstra pode dar resultados errados quando alguns pesos de aresta são negativos?

1. AEntra num laço infinito a cada aresta negativa
2. BUm vértice é finalizado ao ser extraído, mas uma aresta negativa posterior ainda poderia dar a ele um caminho mais curto
3. CNúmeros negativos não podem ser armazenados numa fila de prioridade
4. DSó funciona em grafos não dirigidos

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 log n)
4. DΘ(n³)