Lista de exercícios de Algoritmos e complexidade com respostas

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. BCerca de n / 2
3. CCerca de n
4. DCerca de log₂ n

O tempo de execução de um algoritmo é O(n). Como se chama esse crescimento?

1. AConstante
2. BLogarítmico
3. CLinear
4. DQuadrático

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

1. AMerge sort
2. BBubble sort
3. CQuicksort
4. DInsertion sort

Por que a programação dinâmica não traz ganho real de velocidade para o merge sort?

1. AO merge sort não tem estrutura recursiva
2. BSeus subproblemas não se sobrepõem, então não há nada para reaproveitar
3. CA programação dinâmica só funciona em problemas de grafos, não em vetores
4. DO merge sort já é O(n)

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

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

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

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

O que o teorema de Cook–Levin estabeleceu?

1. AO problema da satisfatibilidade booleana (SAT) é NP-completo
2. BP é diferente de NP
3. CTodo problema NP pode ser resolvido em tempo exponencial
4. DO problema da parada é indecidível

Por que a busca binária não dá tempo O(log n) numa lista simplesmente encadeada?

1. AA busca binária precisa de pelo menos o dobro da memória
2. BAs comparações entre nós de lista encadeada são mais lentas
3. CListas encadeadas não podem ser ordenadas
4. DChegar ao elemento do meio leva O(n) passos, pois não há acesso direto por índice