Lista de exercícios de Algoritmos e complexidade com respostas

Qual é o tempo de execução do counting sort para n inteiros no intervalo de 0 a k?

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

Um algoritmo O(n) leva 3 segundos para n = 1 milhão. Quanto tempo leva, aproximadamente, para n = 2 milhões?

1. A6 segundos
2. B12 segundos
3. C9 segundos
4. D3 segundos

Quais são as três etapas de um algoritmo de divisão e conquista?

1. AChutar, verificar, repetir
2. BDividir, conquistar, combinar
3. CLer, calcular, escrever
4. DOrdenar, buscar, retornar

Por que a programação dinâmica não traz ganho real de velocidade para o merge sort?

1. AO merge sort já é O(n)
2. BO merge sort não tem estrutura recursiva
3. CSeus subproblemas não se sobrepõem, então não há nada para reaproveitar
4. DA programação dinâmica só funciona em problemas de grafos, não em vetores

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

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

Qual é a complexidade de tempo de multiplicar duas matrizes n × n com o laço triplo padrão?

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

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

Por que a busca média em uma tabela hash é O(1), mas o pior caso é O(n)?

1. AArrays têm acesso O(n)
2. BAs chaves precisam ser ordenadas primeiro
3. CMuitas chaves podem colidir no mesmo bucket
4. DFunções hash são lentas