Lista de exercícios de Algoritmos e complexidade com respostas

O que é o caso base de uma função recursiva?

1. AA primeira linha da função
2. BA chamada que usa mais memória
3. CO caso com a maior entrada, que é tratado antes de quaisquer chamadas recursivas
4. DUm caso respondido diretamente, sem fazer outra chamada recursiva

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

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

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²

A programação dinâmica é útil quando um problema tem:

1. ASubproblemas sobrepostos e subestrutura ótima
2. BNenhum subproblema, de modo que pode ser resolvido em um único passo
3. CApenas entradas aleatórias
4. DUm único laço

Uma função executa um laço de n iterações e depois, separadamente, outro laço de n iterações. Qual é a sua complexidade de tempo?

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

Quantos níveis tem a recursão do merge sort para um array de n elementos?

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

Qual afirmação sobre selecionar o k-ésimo menor elemento de um array não ordenado está correta?

1. AA seleção sempre exige Ω(n log n), porque requer ordenação
2. BA seleção só é possível em O(n²)
3. CO quickselect roda em O(n) esperado, e a mediana das medianas garante O(n) no pior caso
4. DO quickselect roda em O(log n) no pior caso, porque faz recursão em apenas um lado do pivô

Caminhos simples mínimos podem ser encontrados em tempo polinomial. O que se sabe sobre encontrar o caminho simples mais longo entre dois vértices num grafo geral?

1. AÉ NP-difícil
2. BÉ indecidível
3. CPode ser resolvido pelo algoritmo de Dijkstra com os pesos negados
4. DÉ sempre solúvel em O(V + E)