Lista de exercícios de Algoritmos e complexidade com respostas

Qual é a complexidade de tempo da busca linear em um array não ordenado com n elementos (pior caso)?

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

O que é um algoritmo?

1. AQualquer programa de computador com interface gráfica
2. BUma linguagem de programação criada para escrever fórmulas matemáticas
3. CUma sequência finita de passos bem definidos que resolve um problema
4. DUma estrutura de dados que armazena números

Qual algoritmo de ordenação escolhe um pivô e particiona o array em elementos menores e maiores?

1. AMerge sort
2. BQuicksort
3. CInsertion sort
4. DBubble sort

Qual é a solução da recorrência T(n) = 2T(n/2) + O(1)?

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

O que o algoritmo de Floyd–Warshall calcula, e com que rapidez?

1. AUma ordenação topológica em O(V²)
2. BCaminhos mínimos de um vértice de origem para todos os outros em O(V + E)
3. CUma árvore geradora mínima em O(E log V)
4. DCaminhos mínimos entre todos os pares de vértices em O(V³)

O problema da parada mostra que:

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

Qual destes problemas de satisfatibilidade é sabidamente solúvel em tempo polinomial?

1. ASatisfatibilidade de circuitos
2. B2-SAT, em que cada cláusula tem no máximo dois literais
3. C3-SAT, em que cada cláusula tem exatamente três literais
4. DSAT geral em fórmulas na forma normal conjuntiva