Lista de exercícios de Algoritmos e complexidade com respostas

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 esperado que leva com uma entrada aleatória de tamanho n
3. CO tempo que leva num computador lento
4. DO tempo que leva com a menor entrada

Qual destes tempos de execução é polinomial?

1. AO(2ⁿ)
2. BO(nⁿ)
3. CO(n³)
4. DO(n!)

Qual é o O grande de 3n² + 5n + 2?

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

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

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

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

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

Um algoritmo guloso (greedy):

1. ATesta todas as soluções possíveis
2. BUsa apenas recursão
3. CSempre fornece a solução ótima
4. DFaz a melhor escolha local em cada passo

Tomar as duas extremidades de cada aresta de um emparelhamento maximal dá uma cobertura de vértices. Quão boa é essa cobertura?

1. ADe qualidade desconhecida em relação ao ótimo
2. BSempre uma cobertura de vértices mínima
3. CNo máximo log n vezes o mínimo
4. DNo máximo o dobro do tamanho de uma cobertura de vértices mínima

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

1. AAs comparações entre nós de lista encadeada são mais lentas
2. BListas encadeadas não podem ser ordenadas
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