Lista de exercícios de Algoritmos e complexidade com respostas

Qual é a complexidade de tempo do insertion sort no pior caso?

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

Um algoritmo com dois laços aninhados, cada um executado n vezes, normalmente tem qual complexidade?

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

Quais são as três etapas de um algoritmo de divisão e conquista?

1. AChutar, verificar, repetir
2. BLer, calcular, escrever
3. COrdenar, buscar, retornar
4. DDividir, conquistar, combinar

A complexidade de tempo do Fibonacci recursivo ingênuo (fib(n) = fib(n−1) + fib(n−2)) é:

1. ALogarítmica
2. BLinear
3. CConstante
4. DExponencial

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

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

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

Qual definição da classe NP está correta?

1. AProblemas que nenhum algoritmo consegue resolver
2. BProblemas que não podem ser resolvidos em tempo polinomial
3. CProblemas que não são polinomiais
4. DProblemas de decisão cujas respostas "sim" podem ser verificadas em tempo polinomial dado um certificado

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

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