Lista de exercícios de Algoritmos e complexidade com respostas

Qual destas cresce mais devagar quando n fica grande?

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

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

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

O que a busca binária exige da sua entrada?

1. AO array não pode ter mais de 1000 elementos
2. BO array deve conter só números positivos
3. CO array deve estar ordenado
4. DO tamanho do array deve ser uma potência de dois

Como o algoritmo de Prim constrói uma árvore geradora mínima?

1. ARemove a aresta mais cara até não restarem ciclos
2. BOrdena todas as arestas por peso e adiciona cada uma, a menos que forme um ciclo na floresta
3. CExecuta uma busca em largura e mantém a árvore da BFS
4. DFaz crescer uma árvore a partir de um vértice inicial, adicionando a aresta mais barata que sai da árvore

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 100
3. CCerca de 20
4. DCerca de 1,000

Qual é a solução da recorrência T(n) = T(n − 1) + O(n)?

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

Qual é a complexidade de tempo para construir um heap binário a partir de n elementos não ordenados com o método bottom-up?

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

O algoritmo de Strassen multiplica matrizes usando 7, em vez de 8, multiplicações recursivas de blocos de metade do tamanho. Qual é o seu tempo de execução?

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n^{log₂ 7}), cerca de n^2,81