Lista de exercícios de Algoritmos e complexidade com respostas

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 que leva com a menor entrada
3. CO tempo que leva num computador lento
4. DO tempo esperado que leva com uma entrada aleatória de tamanho n

Quais são as três etapas de um algoritmo de divisão e conquista?

1. ALer, calcular, escrever
2. BOrdenar, buscar, retornar
3. CDividir, conquistar, combinar
4. DChutar, verificar, repetir

Qual classe de complexidade cresce mais rápido para n grande?

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

Qual é a complexidade de tempo do algoritmo padrão de programação dinâmica para a maior subsequência comum de strings de comprimentos m e n?

1. AO(mn log n)
2. BO(2^m+n)
3. CO(m + n)
4. DO(mn)

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

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

Qual algoritmo encontra os caminhos mínimos a partir de uma origem em um grafo com pesos de arestas não negativos?

1. AAlgoritmo de Dijkstra
2. BAlgoritmo de Kruskal
3. CBellman-Ford é necessário em todos os casos
4. DBusca em profundidade (DFS)

Como é classificado o problema do caixeiro-viajante?

1. AA versão de decisão é NP-completa e a versão de otimização é NP-difícil
2. BEstá em P, porque o algoritmo de Dijkstra o resolve visitando cada cidade uma única vez
3. CÉ indecidível
4. DA versão de decisão está em P, mas a versão de otimização é NP-completa

Quais são os custos de tempo e espaço de calcular o n-ésimo número de Fibonacci com um laço que guarda só os dois últimos valores?

1. ATempo O(n) e espaço O(1)
2. BTempo O(n) e espaço O(n)
3. CTempo O(log n) e espaço O(n)
4. DTempo O(2ⁿ) e espaço O(1)