Lista de exercícios de Algoritmos e complexidade com respostas

Qual é a complexidade de tempo para encontrar o maior valor num array não ordenado de n números?

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

O que significa uma operação rodar em tempo O(1)?

1. AProcessa exatamente um elemento por segundo de tempo de execução
2. BSó pode ser executada uma vez
3. CSeu tempo de execução não cresce com o tamanho da entrada
4. DSempre leva exatamente um segundo

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)

Uma função executa um laço de n iterações e depois, separadamente, outro laço de n iterações. Qual é a sua complexidade de tempo?

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

Um algoritmo guloso (greedy):

1. AFaz a melhor escolha local em cada passo
2. BUsa apenas recursão
3. CSempre fornece a solução ótima
4. DTesta todas as soluções possíveis

Por que a programação dinâmica não traz ganho real de velocidade para o merge sort?

1. ASeus subproblemas não se sobrepõem, então não há nada para reaproveitar
2. BO merge sort já é O(n)
3. CA programação dinâmica só funciona em problemas de grafos, não em vetores
4. DO merge sort não tem estrutura recursiva

Para mostrar que um novo problema X é NP-difícil, o que você precisa fazer?

1. AReduzir X a um problema NP-difícil conhecido em tempo polinomial
2. BReduzir um problema NP-difícil conhecido a X em tempo polinomial
3. CMostrar que X não tem algoritmo polinomial para entradas pequenas
4. DMostrar que X pode ser verificado em tempo polinomial

Como o algoritmo de Bellman–Ford detecta um ciclo de peso negativo alcançável a partir da origem?

1. AVerifica se alguma aresta tem peso negativo
2. BExecuta o algoritmo de Dijkstra duas vezes e compara os dois resultados de distância
3. CConta os ciclos com busca em profundidade
4. DApós V − 1 rodadas, verifica se alguma aresta ainda pode ser relaxada