Lista de exercícios de Algoritmos e complexidade com respostas

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

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

Qual notação descreve um limite superior de crescimento?

1. AO grande (Big O)
2. BÔmega grande (Big Omega)
3. CÔmega pequeno (little omega)
4. DTheta grande (Big Theta)

Qual algoritmo de ordenação troca repetidamente elementos adjacentes que estão na ordem errada?

1. AHeap sort
2. BMerge sort (ordenação por intercalação)
3. CBubble sort (ordenação por bolha)
4. DQuicksort

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. AO compilador sempre a transforma em um laço que termina com segurança
2. BEla roda em tempo O(1)
3. CEla continua chamando a si mesma até a pilha de chamadas estourar
4. DEla retorna 0 automaticamente

Qual é a complexidade de tempo do algoritmo padrão de programação dinâmica para a maior subsequência comum de strings de comprimentos m e n?

1. AO(m + n)
2. BO(2^m+n)
3. CO(mn log n)
4. DO(mn)

Por que o algoritmo de Dijkstra pode dar resultados errados quando alguns pesos de aresta são negativos?

1. AUm vértice é finalizado ao ser extraído, mas uma aresta negativa posterior ainda poderia dar a ele um caminho mais curto
2. BSó funciona em grafos não dirigidos
3. CNúmeros negativos não podem ser armazenados numa fila de prioridade
4. DEntra num laço infinito a cada aresta negativa

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³)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n^{log₂ 7}), cerca de n^2,81