Lista de exercícios de Algoritmos e complexidade com respostas

Qual é a complexidade de tempo da busca em profundidade num grafo armazenado como listas de adjacência?

1. AO(V²)
2. BO(V × E)
3. CO(E log V)
4. DO(V + E)

Qual é a complexidade de tempo do merge sort no pior caso?

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

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

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

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

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

Qual é a complexidade de tempo de multiplicar duas matrizes n × n com o laço triplo padrão?

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

Um algoritmo guloso (greedy):

1. AUsa apenas recursão
2. BTesta todas as soluções possíveis
3. CFaz a melhor escolha local em cada passo
4. DSempre fornece a solução ótima

Qual é a diferença entre um problema indecidível e um intratável?

1. ANenhum algoritmo resolve um problema indecidível para todas as entradas, enquanto um intratável tem algoritmo, mas é lento demais
2. BProblemas indecidíveis estão em NP, enquanto os intratáveis estão em P
3. CAmbos significam que o problema não tem nenhum algoritmo
4. DProblemas intratáveis não podem ser resolvidos por nenhum algoritmo, enquanto os indecidíveis só exigem tempo exponencial

Para qual variante da mochila a regra gulosa "pegar os itens em ordem de valor por peso" sempre dá uma resposta ótima?

1. AA mochila fracionária, em que os itens podem ser divididos
2. BAs duas variantes
3. CNenhuma das variantes
4. DA mochila 0/1, em que os itens devem ser sempre levados inteiros