Lista de exercícios de Algoritmos e complexidade com respostas

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

Acessar um elemento de um array pelo índice leva:

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

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

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

Com moedas de 1, 3 e 4 e um valor de 6, quantas moedas o método guloso "maior moeda primeiro" usa, em comparação com o ótimo?

1. AO guloso usa 3 moedas; o ótimo é 2
2. BO guloso usa 4 moedas; o ótimo é 3
3. CO guloso usa 2 moedas; o ótimo é 2
4. DO guloso usa 3 moedas; o ótimo é 3

Num array ordenado, você procura dois elementos cuja soma seja um alvo movendo um ponteiro de cada extremidade para dentro. Qual é a complexidade de tempo?

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

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

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

Qual afirmação sobre a notação o pequeno está correta?

1. An = o(n), já que toda função é o pequeno de si mesma
2. Bn = o(n²), mas n não é o(n)
3. Cn² = o(n)
4. D2n = o(n), porque 2n cresce devagar

Quais são os custos de tempo e espaço de calcular o n-ésimo número de Fibonacci com um laço que guarda só os dois últimos valores?

1. ATempo O(log n) e espaço O(n)
2. BTempo O(n) e espaço O(1)
3. CTempo O(n) e espaço O(n)
4. DTempo O(2ⁿ) e espaço O(1)