Lista de exercícios de Algoritmos e complexidade com respostas

A complexidade de espaço mede:

1. AO número de linhas de código
2. BO tamanho físico do computador
3. CA quantidade de memória que um algoritmo precisa à medida que a entrada cresce
4. DO espaço em disco do arquivo do programa depois de compilado

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

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

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

1. ALinear
2. BLogarítmico
3. CQuadrático
4. DConstante

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

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

Com moedas de 1, 3 e 4 e um valor de 6, quantas moedas o método guloso "maior moeda primeiro" usa, em comparação com o ótimo?

1. AO guloso usa 4 moedas; o ótimo é 3
2. BO guloso usa 3 moedas; o ótimo é 2
3. CO guloso usa 2 moedas; o ótimo é 2
4. DO guloso usa 3 moedas; o ótimo é 3

No problema de seleção de atividades, qual regra gulosa sempre dá o número máximo de atividades sem sobreposição?

1. AEscolher a atividade que começa mais cedo
2. BEscolher primeiro a atividade mais curta
3. CEscolher a atividade que termina mais cedo e repetir com as compatíveis
4. DEscolher primeiro a atividade com menos sobreposições e repetir com as compatíveis

Para qual variante da mochila a regra gulosa "pegar os itens em ordem de valor por peso" sempre dá uma resposta ótima?

1. AAs duas variantes
2. BA mochila 0/1, em que os itens devem ser sempre levados inteiros
3. CNenhuma das variantes
4. DA mochila fracionária, em que os itens podem ser divididos

O problema da mochila 0/1 resolvido com programação dinâmica leva tempo O(nW). Por que isso é chamado de pseudopolinomial?

1. APorque só funciona para W = 0
2. BPorque o algoritmo é aleatorizado e seu tempo de execução varia a cada entrada
3. CW é um número, então o tempo é exponencial no número de bits usados para escrever W
4. DPorque n é sempre pequeno