Lista de exercícios de Algoritmos e complexidade com respostas

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

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

O que é recursão?

1. AUma função que chama a si mesma com entradas menores
2. BUm laço que nunca termina
3. CUm tipo de estrutura de dados
4. DUm método de ordenação

O que a busca binária exige da sua entrada?

1. AO array deve estar ordenado
2. BO array deve conter só números positivos
3. CO array não pode ter mais de 1000 elementos
4. DO tamanho do array deve ser uma potência de dois

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)

Por que a base do logaritmo costuma ser omitida no O grande, como em O(log n)?

1. AOs logaritmos são sempre arredondados para inteiros
2. BLogaritmos de bases diferentes diferem apenas por um fator constante
3. CTodos os logaritmos em computação têm base 10, então ela fica implícita
4. DA base só importa para n pequeno

Qual é a complexidade de tempo de calcular o n-ésimo número de Fibonacci com uma tabela bottom-up?

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

O insertion sort roda em O(n) com entrada ordenada. Isso contradiz o limite inferior Ω(n log n) da ordenação por comparação?

1. ASim, portanto o limite inferior está errado
2. BNão, porque o insertion sort não é uma ordenação por comparação
3. CSim, mas só para arrays com menos de 100 elementos
4. DNão, o limite inferior vale para o pior caso entre todas as entradas, não para cada entrada

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. BDe qualidade desconhecida em relação ao ótimo
3. CSempre uma cobertura de vértices mínima
4. DNo máximo log n vezes o mínimo