Lista de exercícios de Algoritmos e complexidade com respostas

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

1. A4 segundos
2. B1 segundo
3. C2 segundos
4. D8 segundos

Um problema costuma ser chamado de tratável se:

1. ASó pode ser resolvido testando todas as possibilidades
2. BNão tem solução
3. CPode ser resolvido em tempo constante
4. DPode ser resolvido em tempo polinomial

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

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

Por que a base do logaritmo costuma ser omitida no O grande, como em O(log n)?

1. AA base só importa para n pequeno
2. BTodos os logaritmos em computação têm base 10, então ela fica implícita
3. COs logaritmos são sempre arredondados para inteiros
4. DLogaritmos de bases diferentes diferem apenas por um fator constante

Qual é a complexidade de tempo de multiplicar duas matrizes n × n com o laço triplo padrão?

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

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 é O(n log n) no pior caso
3. CO insertion sort tem pouco overhead e é rápido com entradas pequenas ou quase ordenadas
4. DAlgoritmos recursivos não conseguem lidar com arrays de menos de 10 elementos

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

1. AProblemas cujas soluções podem ser verificadas, mas nunca encontradas, em tempo polinomial
2. BProblemas de decisão solúveis por um algoritmo determinístico em tempo polinomial
3. CProblemas que exigem tempo exponencial em qualquer computador
4. DProblemas que podem ser resolvidos em paralelo

Como n! e 2ⁿ se comparam para n grande?

1. ACrescem no mesmo ritmo
2. Bn! é O(n²)
3. C2ⁿ cresce mais rápido que n!
4. Dn! cresce mais rápido que 2ⁿ