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(n)
2. BO(n log n)
3. CO(1)
4. DO(log n)

Um algoritmo O(n) leva 3 segundos para n = 1 milhão. Quanto tempo leva, aproximadamente, para n = 2 milhões?

1. A9 segundos
2. B3 segundos
3. C12 segundos
4. D6 segundos

O que é um algoritmo?

1. AUma sequência finita de passos bem definidos que resolve um problema
2. BQualquer programa de computador com interface gráfica
3. CUma linguagem de programação criada para escrever fórmulas matemáticas
4. DUma estrutura de dados que armazena números

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

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

Qual algoritmo de ordenação é estável?

1. ASelection sort (versão típica)
2. BMerge sort
3. CHeap sort
4. DQuicksort (versão in-place típica)

Com moedas de 1, 3 e 4 e um valor de 6, quantas moedas o método guloso "maior moeda primeiro" usa, em comparação com o ótimo?

1. AO guloso usa 4 moedas; o ótimo é 3
2. BO guloso usa 2 moedas; o ótimo é 2
3. CO guloso usa 3 moedas; o ótimo é 3
4. DO guloso usa 3 moedas; o ótimo é 2

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

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

Qual afirmação sobre a notação o pequeno está correta?

1. An² = o(n)
2. Bn = o(n), já que toda função é o pequeno de si mesma
3. C2n = o(n), porque 2n cresce devagar
4. Dn = o(n²), mas n não é o(n)