Lista de exercícios de Algoritmos e complexidade com respostas

Quanta memória extra usa um merge sort padrão baseado em arrays?

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

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

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

Um problema costuma ser chamado de tratável se:

1. APode ser resolvido em tempo constante
2. BSó pode ser resolvido testando todas as possibilidades
3. CNão tem solução
4. DPode ser resolvido em tempo polinomial

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³)
4. DO(n² log n)

O limite inferior para ordenação baseada em comparações no pior caso é:

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

É correto dizer que um algoritmo O(n²) também é O(n³)?

1. ASim, porque o O grande é um limite superior e n² não cresce mais rápido que n³
2. BSim, mas só se n for menor que 100
3. CNão, porque n³ é menor que n² para n grande
4. DNão, porque o O grande deve sempre dar a taxa de crescimento exata da função

Qual é a solução da recorrência T(n) = 2T(n/2) + n log n?

1. AΘ(n log n)
2. BΘ(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. AVerifica se alguma aresta tem peso negativo
2. BApós V − 1 rodadas, verifica se alguma aresta ainda pode ser relaxada
3. CConta os ciclos com busca em profundidade
4. DExecuta o algoritmo de Dijkstra duas vezes e compara os dois resultados de distância