Lista de exercícios de Algoritmos e complexidade com respostas

O que descreve o tempo de execução no caso médio?

1. AO tempo no computador mais comum
2. BO tempo para uma entrada de comprimento médio
3. CO valor intermediário entre os tempos de execução do melhor e do pior caso
4. DO tempo esperado sobre uma dada distribuição de entradas de tamanho n

Qual é a complexidade de tempo da busca binária em um array ordenado?

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

O que significa uma operação rodar em tempo O(1)?

1. ASó pode ser executada uma vez
2. BProcessa exatamente um elemento por segundo de tempo de execução
3. CSempre leva exatamente um segundo
4. DSeu tempo de execução não cresce com o tamanho da entrada

Qual é a solução da recorrência T(n) = T(n − 1) + O(n)?

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

A programação dinâmica é útil quando um problema tem:

1. AApenas entradas aleatórias
2. BSubproblemas sobrepostos e subestrutura ótima
3. CUm único laço
4. DNenhum subproblema, de modo que pode ser resolvido em um único passo

Você ordena um array de n elementos uma vez e depois responde a k consultas de pertinência com busca binária. Qual é o custo total?

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

Por que a busca binária não dá tempo O(log n) numa lista simplesmente encadeada?

1. AListas encadeadas não podem ser ordenadas
2. BAs comparações entre nós de lista encadeada são mais lentas
3. CA busca binária precisa de pelo menos o dobro da memória
4. DChegar ao elemento do meio leva O(n) passos, pois não há acesso direto por índice

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

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