Lista de exercícios de Algoritmos e complexidade com respostas

Quanto é log₂ 1024?

1. A10
2. B12
3. C512
4. D32

Um algoritmo O(n²) leva 1 segundo para n = 1000. Quanto tempo leva, aproximadamente, para n = 2000?

1. A4 segundos
2. B1 segundo
3. C8 segundos
4. D2 segundos

Qual é a complexidade de tempo do insertion sort no melhor caso, com um array já ordenado?

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

Um quicksort usa sempre o primeiro elemento como pivô. Com qual entrada ele apresenta o comportamento de pior caso?

1. AUm array em ordem aleatória
2. BUm array com todos os elementos diferentes
3. CUm array de tamanho 2
4. DUm array que já está ordenado

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

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

O que a análise amortizada mede?

1. AO custo da operação individual mais cara em qualquer ponto da sequência
2. BO custo de um algoritmo com a melhor entrada
3. CO custo esperado sobre entradas aleatórias
4. DO custo médio por operação ao longo de uma sequência de operações de pior caso

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

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

A ordenação topológica só é possível para:

1. AGrafos completos
2. BGrafos não dirigidos
3. CGrafos acíclicos dirigidos (DAG)
4. DGrafos com pesos negativos