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

Qual é o tempo de execução do counting sort para n inteiros no intervalo de 0 a k?

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

Um algoritmo O(n) leva 3 segundos para n = 1 milhão. Quanto tempo leva, aproximadamente, para n = 2 milhões?

1. A6 segundos
2. B3 segundos
3. C12 segundos
4. D9 segundos

Qual é a complexidade de tempo do algoritmo padrão de programação dinâmica para a maior subsequência comum de strings de comprimentos m e n?

1. AO(2^m+n)
2. BO(mn)
3. CO(mn log n)
4. DO(m + n)

Qual afirmação sobre uma função recursiva sem caso base alcançável está correta?

1. AEla continua chamando a si mesma até a pilha de chamadas estourar
2. BO compilador sempre a transforma em um laço que termina com segurança
3. CEla retorna 0 automaticamente
4. DEla roda em tempo O(1)

Por que muitas rotinas de ordenação de bibliotecas passam para o insertion sort em subarrays muito pequenos?

1. AO insertion sort é O(n log n) no pior caso
2. BAlgoritmos recursivos não conseguem lidar com arrays de menos de 10 elementos
3. CO insertion sort tem pouco overhead e é rápido com entradas pequenas ou quase ordenadas
4. DO insertion sort usa menos memória que qualquer outro algoritmo de ordenação em entradas grandes

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

Qual é a complexidade de tempo de: for i = 1 to n: for (j = i; j ≤ n; j = j + i) faça trabalho O(1)?

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