Lista de exercícios de Algoritmos e complexidade com respostas

Qual destes tempos de execução é polinomial?

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

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

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

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

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

Como o algoritmo de Prim constrói uma árvore geradora mínima?

1. ARemove a aresta mais cara até não restarem ciclos
2. BExecuta uma busca em largura e mantém a árvore da BFS
3. COrdena todas as arestas por peso e adiciona cada uma, a menos que forme um ciclo na floresta
4. DFaz crescer uma árvore a partir de um vértice inicial, adicionando a aresta mais barata que sai da árvore

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 é a solução da recorrência T(n) = T(n/2) + O(1)?

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

O insertion sort roda em O(n) com entrada ordenada. Isso contradiz o limite inferior Ω(n log n) da ordenação por comparação?

1. ASim, portanto o limite inferior está errado
2. BSim, mas só para arrays com menos de 100 elementos
3. CNão, porque o insertion sort não é uma ordenação por comparação
4. DNão, o limite inferior vale para o pior caso entre todas as entradas, não para cada entrada

Como é classificado o problema do caixeiro-viajante?

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