Lista de exercícios de Algoritmos e complexidade com respostas

A complexidade de espaço mede:

1. AO número de linhas de código
2. BO tamanho físico do computador
3. CA quantidade de memória que um algoritmo precisa à medida que a entrada cresce
4. DO espaço em disco do arquivo do programa depois de compilado

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

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

Quanta memória extra usa um merge sort padrão baseado em arrays?

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

A recorrência T(n) = 2T(n/2) + O(n) tem como solução:

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

O que o algoritmo de Floyd–Warshall calcula, e com que rapidez?

1. ACaminhos mínimos entre todos os pares de vértices em O(V³)
2. BUma árvore geradora mínima em O(E log V)
3. CUma ordenação topológica em O(V²)
4. DCaminhos mínimos de um vértice de origem para todos os outros em O(V + E)

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 tem pouco overhead e é rápido com entradas pequenas ou quase ordenadas
3. CO insertion sort usa menos memória que qualquer outro algoritmo de ordenação em entradas grandes
4. DAlgoritmos recursivos não conseguem lidar com arrays de menos de 10 elementos

Qual técnica dá ao quicksort um tempo de execução esperado O(n log n) para qualquer entrada?

1. AOrdenar a entrada antes de executar o quicksort
2. BUsar recursão apenas no lado esquerdo
3. CSempre escolher o primeiro elemento
4. DEscolher o pivô de forma uniformemente aleatória

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)