Lista de exercícios de Algoritmos e complexidade com respostas

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 n
3. CCerca de log₂ n
4. DCerca de n / 2

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(1)
3. CO(n)
4. DO(n²)

Qual algoritmo de ordenação troca repetidamente elementos adjacentes que estão na ordem errada?

1. AHeap sort
2. BQuicksort
3. CMerge sort (ordenação por intercalação)
4. DBubble sort (ordenação por bolha)

Qual é a complexidade de tempo do algoritmo de Bellman–Ford num grafo com V vértices e E arestas?

1. AO(E log V)
2. BO(V + E)
3. CO(V³ × E)
4. DO(V × E)

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

1. AHeap sort
2. BMerge sort
3. CQuicksort (versão in-place típica)
4. DSelection sort (versão típica)

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

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

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

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

O problema da mochila 0/1 resolvido com programação dinâmica leva tempo O(nW). Por que isso é chamado de pseudopolinomial?

1. APorque só funciona para W = 0
2. BPorque o algoritmo é aleatorizado e seu tempo de execução varia a cada entrada
3. CW é um número, então o tempo é exponencial no número de bits usados para escrever W
4. DPorque n é sempre pequeno