Lista de exercícios de Algoritmos e complexidade com respostas

Qual é a complexidade de tempo do insertion sort no pior caso?

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

O que descreve o tempo de execução de um algoritmo no pior caso?

1. AO tempo que leva com a menor entrada
2. BO tempo máximo que ele leva entre todas as entradas de tamanho n
3. CO tempo que leva num computador lento
4. DO tempo esperado que leva com uma entrada aleatória de tamanho n

Um algoritmo O(n²) leva 1 segundo para n = 1000. Quanto tempo leva, aproximadamente, para n = 2000?

1. A4 segundos
2. B2 segundos
3. C1 segundo
4. D8 segundos

A busca em largura (BFS) em um grafo não ponderado encontra:

1. AA árvore geradora mínima
2. BUma ordenação topológica em todos os grafos
3. CCaminhos mínimos em grafos que contêm arestas com pesos negativos
4. DCaminhos mínimos em número de arestas a partir do nó inicial

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

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

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

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, mas só para arrays com menos de 100 elementos
2. BNão, porque o insertion sort não é uma ordenação por comparação
3. CNão, o limite inferior vale para o pior caso entre todas as entradas, não para cada entrada
4. DSim, portanto o limite inferior está errado

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

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