Lista de exercícios de Algoritmos e complexidade com respostas

Acessar um elemento de um array pelo índice leva:

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

A complexidade de espaço mede:

1. AO tamanho físico do computador
2. BA quantidade de memória que um algoritmo precisa à medida que a entrada cresce
3. CO número de linhas de código
4. DO espaço em disco do arquivo do programa depois de compilado

Um laço começa com i = 1 e dobra i a cada iteração até i > n. Quantas iterações ele executa?

1. ACerca de n / 2
2. BCerca de log₂ n
3. CCerca de n²
4. DCerca de n

Num array ordenado, você procura dois elementos cuja soma seja um alvo movendo um ponteiro de cada extremidade para dentro. Qual é a complexidade de tempo?

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

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(nk)
2. BO(n log n + k log n)
3. CO(n + k)
4. DO(k n log n)

É correto dizer que um algoritmo O(n²) também é O(n³)?

1. ANão, porque n³ é menor que n² para n grande
2. BNão, porque o O grande deve sempre dar a taxa de crescimento exata da função
3. CSim, mas só se n for menor que 100
4. DSim, porque o O grande é um limite superior e n² não cresce mais rápido que n³

O problema da parada mostra que:

1. AAlguns programas rodam mais rápido em computadores mais rápidos, então a parada depende do hardware
2. BTodo programa acaba parando
3. CLaços devem ser evitados
4. DNenhum algoritmo consegue decidir, para todo programa e toda entrada, se o programa para

O algoritmo de programação dinâmica de Held–Karp resolve o problema do caixeiro-viajante de forma exata. Qual é o seu tempo de execução para n cidades?

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