Lista de exercícios de Algoritmos e complexidade com respostas

O que é memoização?

1. AEscrever comentários ao lado de cada linha de código
2. BConverter automaticamente a recursão em um laço equivalente, de modo que não seja preciso pilha de chamadas
3. CLiberar memória depois que uma função retorna
4. DArmazenar os resultados de chamadas de função para que chamadas repetidas sejam respondidas da memória

O que descreve o tempo de execução de um algoritmo no pior caso?

1. AO tempo máximo que ele leva entre todas as entradas de tamanho n
2. BO tempo esperado que leva com uma entrada aleatória de tamanho n
3. CO tempo que leva com a menor entrada
4. DO tempo que leva num computador lento

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

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

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

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

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

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

Qual é a complexidade de tempo de calcular o n-ésimo número de Fibonacci com uma tabela bottom-up?

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

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

1. A2ⁿ cresce mais rápido que n!
2. BCrescem no mesmo ritmo
3. Cn! cresce mais rápido que 2ⁿ
4. Dn! é O(n²)

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

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