Lista de exercícios de Algoritmos e complexidade com respostas

O tempo de execução de um algoritmo é O(n). Como se chama esse crescimento?

1. ALogarítmico
2. BLinear
3. CConstante
4. DQuadrático

Um algoritmo O(n²) leva 1 segundo para n = 1000. Quanto tempo leva, aproximadamente, para n = 2000?

1. A2 segundos
2. B1 segundo
3. C8 segundos
4. D4 segundos

O que descreve o tempo de execução de um algoritmo no pior caso?

1. AO tempo que leva com a menor entrada
2. BO tempo máximo que ele leva entre todas as entradas de tamanho n
3. CO tempo esperado que leva com uma entrada aleatória de tamanho n
4. DO tempo que leva num computador lento

Qual é a complexidade de tempo de: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Quanto espaço de pilha usa uma função fatorial recursiva simples fact(n) = n × fact(n − 1)?

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

Qual afirmação sobre uma função recursiva sem caso base alcançável está correta?

1. AEla continua chamando a si mesma até a pilha de chamadas estourar
2. BEla retorna 0 automaticamente
3. CEla roda em tempo O(1)
4. DO compilador sempre a transforma em um laço que termina com segurança

Tomar as duas extremidades de cada aresta de um emparelhamento maximal dá uma cobertura de vértices. Quão boa é essa cobertura?

1. ANo máximo o dobro do tamanho de uma cobertura de vértices mínima
2. BSempre uma cobertura de vértices mínima
3. CDe qualidade desconhecida em relação ao ótimo
4. DNo máximo log n vezes o mínimo

Qual afirmação sobre P e NP está correta?

1. ANP significa "não polinomial"
2. BTodo problema em P também está em NP
3. CSoluções de problemas NP não podem ser verificadas rapidamente
4. DFoi provado que P ≠ NP