Lista de exercícios de Algoritmos e complexidade com respostas

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

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

O que é memoização?

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

Como funciona o selection sort?

1. AEncontra repetidamente o mínimo da parte não ordenada e o troca para a frente
2. BTroca repetidamente elementos vizinhos que estão na ordem errada
3. CInsere cada elemento numa parte ordenada crescente por deslocamento
4. DDivide o array em metades e as intercala

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

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

O que a análise amortizada mede?

1. AO custo da operação individual mais cara em qualquer ponto da sequência
2. BO custo esperado sobre entradas aleatórias
3. CO custo médio por operação ao longo de uma sequência de operações de pior caso
4. DO custo de um algoritmo com a melhor entrada

Qual é a complexidade de tempo do quicksort no pior caso?

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

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

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

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

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