Lista de exercícios de Algoritmos e complexidade com respostas

Qual classe de complexidade cresce mais rápido para n grande?

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

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

1. AÔmega grande (Big Omega)
2. BÔmega pequeno (little omega)
3. CTheta grande (Big Theta)
4. DO grande (Big O)

Qual é o O grande de 3n² + 5n + 2?

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

Por que muitas rotinas de ordenação de bibliotecas passam para o insertion sort em subarrays muito pequenos?

1. AO insertion sort é O(n log n) no pior caso
2. BO insertion sort usa menos memória que qualquer outro algoritmo de ordenação em entradas grandes
3. CAlgoritmos recursivos não conseguem lidar com arrays de menos de 10 elementos
4. DO insertion sort tem pouco overhead e é rápido com entradas pequenas ou quase ordenadas

Por que a programação dinâmica não traz ganho real de velocidade para o merge sort?

1. AO merge sort já é O(n)
2. BA programação dinâmica só funciona em problemas de grafos, não em vetores
3. CO merge sort não tem estrutura recursiva
4. DSeus subproblemas não se sobrepõem, então não há nada para reaproveitar

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

1. AO(n)
2. BO(2ⁿ)
3. CO(n log n)
4. DO(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 o algoritmo é aleatorizado e seu tempo de execução varia a cada entrada
2. BPorque n é sempre pequeno
3. CPorque só funciona para W = 0
4. DW é um número, então o tempo é exponencial no número de bits usados para escrever W

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

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