Lista de exercícios de Algoritmos e complexidade com respostas

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

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

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

1. ATheta grande (Big Theta)
2. BÔmega grande (Big Omega)
3. CO grande (Big O)
4. DÔmega pequeno (little omega)

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

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

Uma função executa um laço de n iterações e depois, separadamente, outro laço de n iterações. Qual é a sua complexidade de tempo?

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

Qual é o tempo de execução do radix sort LSD para n inteiros com d dígitos na base k?

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

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 continua chamando a si mesma até a pilha de chamadas estourar
3. CEla roda em tempo O(1)
4. DEla retorna 0 automaticamente

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

Como é classificado o problema do caixeiro-viajante?

1. AEstá em P, porque o algoritmo de Dijkstra o resolve visitando cada cidade uma única vez
2. BA versão de decisão é NP-completa e a versão de otimização é NP-difícil
3. CÉ indecidível
4. DA versão de decisão está em P, mas a versão de otimização é NP-completa