Lista de exercícios de Algoritmos e complexidade com respostas

Um algoritmo com dois laços aninhados, cada um executado n vezes, normalmente tem qual complexidade?

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

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

1. AOrdenar, buscar, retornar
2. BLer, calcular, escrever
3. CChutar, verificar, repetir
4. DDividir, conquistar, combinar

Qual é a complexidade de tempo do insertion sort no melhor caso, com um array já ordenado?

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

Aproximadamente quantas comparações a busca binária precisa no pior caso num array ordenado de 1,000,000 de elementos?

1. ACerca de 500,000
2. BCerca de 1,000
3. CCerca de 100
4. DCerca de 20

Qual afirmação sobre uma função recursiva sem caso base alcançável está correta?

1. AEla retorna 0 automaticamente
2. BEla continua chamando a si mesma até a pilha de chamadas estourar
3. CO compilador sempre a transforma em um laço que termina com segurança
4. DEla roda em tempo O(1)

Num array ordenado, você procura dois elementos cuja soma seja um alvo movendo um ponteiro de cada extremidade para dentro. Qual é a complexidade de tempo?

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

Usando o teorema mestre, T(n) = 8T(n/2) + O(n²) tem como solução:

1. AΘ(n²)
2. BΘ(n² log n)
3. CΘ(n³)
4. DΘ(n log n)

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

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