Lista de exercícios de Algoritmos e complexidade com respostas

Qual classe de complexidade cresce mais rápido para n grande?

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

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

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

Qual é o tempo de execução do counting sort para n inteiros no intervalo de 0 a k?

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

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

Qual algoritmo encontra os caminhos mínimos a partir de uma origem em um grafo com pesos de arestas não negativos?

1. ABusca em profundidade (DFS)
2. BAlgoritmo de Kruskal
3. CAlgoritmo de Dijkstra
4. DBellman-Ford é necessário em todos os casos

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

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

Qual é o tempo de execução do algoritmo de Dijkstra com um heap binário num grafo com V vértices e E arestas?

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

Qual algoritmo encontra uma árvore geradora mínima adicionando repetidamente a aresta mais barata que não forma um ciclo?

1. AAlgoritmo de Kruskal
2. BAlgoritmo de Prim a partir de um nó
3. CFloyd-Warshall
4. DAlgoritmo de Dijkstra