Lista de exercícios de Algoritmos e complexidade com respostas

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

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

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

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

Qual destas cresce mais devagar quando n fica grande?

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

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

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

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

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

Um quicksort usa sempre o primeiro elemento como pivô. Com qual entrada ele apresenta o comportamento de pior caso?

1. AUm array com todos os elementos diferentes
2. BUm array em ordem aleatória
3. CUm array que já está ordenado
4. DUm array de tamanho 2

O que o teorema de Cook–Levin estabeleceu?

1. ATodo problema NP pode ser resolvido em tempo exponencial
2. BO problema da parada é indecidível
3. CO problema da satisfatibilidade booleana (SAT) é NP-completo
4. DP é diferente de NP

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 fracionária, em que os itens podem ser divididos
3. CNenhuma das variantes
4. DA mochila 0/1, em que os itens devem ser sempre levados inteiros