Lista de exercícios de Algoritmos e complexidade com respostas

Como se chama o crescimento O(2ⁿ)?

1. APolinomial
2. BLogarítmico
3. CExponencial
4. DLinear

O que a busca binária exige da sua entrada?

1. AO array não pode ter mais de 1000 elementos
2. BO array deve conter só números positivos
3. CO array deve estar ordenado
4. DO tamanho do array deve ser uma potência de dois

O tempo de execução de um algoritmo é O(n). Como se chama esse crescimento?

1. ALinear
2. BQuadrático
3. CLogarítmico
4. DConstante

Quanto espaço de pilha usa uma função fatorial recursiva simples fact(n) = n × fact(n − 1)?

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

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

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

Num array ordenado, você procura dois elementos cuja soma seja um alvo movendo um ponteiro de cada extremidade para dentro. Qual é a complexidade de tempo?

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

Qual destes problemas de satisfatibilidade é sabidamente solúvel em tempo polinomial?

1. ASatisfatibilidade de circuitos
2. B2-SAT, em que cada cláusula tem no máximo dois literais
3. CSAT geral em fórmulas na forma normal conjuntiva
4. D3-SAT, em que cada cláusula tem exatamente três literais

Qual é o custo amortizado de incrementar um contador binário, sabendo que um incremento pode inverter muitos bits?

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