Lista de exercícios de Algoritmos e complexidade com respostas

Qual é a complexidade de tempo do insertion sort no melhor caso, com um array já ordenado?

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

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

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

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

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

Qual é a complexidade de tempo amortizada de adicionar ao final de um array dinâmico que dobra sua capacidade quando fica cheio?

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

Aproximadamente quantas comparações a busca binária precisa no pior caso num array ordenado de 1,000,000 de elementos?

1. ACerca de 20
2. BCerca de 500,000
3. CCerca de 100
4. DCerca de 1,000

O que a análise amortizada mede?

1. AO custo esperado sobre entradas aleatórias
2. BO custo de um algoritmo com a melhor entrada
3. CO custo da operação individual mais cara em qualquer ponto da sequência
4. DO custo médio por operação ao longo de uma sequência de operações de pior caso

O problema da mochila 0/1 resolvido com programação dinâmica leva tempo O(nW). Por que isso é chamado de pseudopolinomial?

1. APorque o algoritmo é aleatorizado e seu tempo de execução varia a cada entrada
2. BPorque n é sempre pequeno
3. CW é um número, então o tempo é exponencial no número de bits usados para escrever W
4. DPorque só funciona para W = 0

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

1. ASempre uma cobertura de vértices mínima
2. BDe qualidade desconhecida em relação ao ótimo
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