Lista de exercícios de Algoritmos e complexidade com respostas

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

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

Acessar um elemento de um array pelo índice leva:

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

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

1. AInsertion sort
2. BBubble sort
3. CMerge sort
4. DQuicksort

Qual é a complexidade de tempo amortizada de adicionar ao final de um array dinâmico que dobra sua capacidade quando fica cheio?

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

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

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

É correto dizer que um algoritmo O(n²) também é O(n³)?

1. ANão, porque n³ é menor que n² para n grande
2. BNão, porque o O grande deve sempre dar a taxa de crescimento exata da função
3. CSim, porque o O grande é um limite superior e n² não cresce mais rápido que n³
4. DSim, mas só se n for menor que 100

O que decorreria se alguém encontrasse um algoritmo de tempo polinomial para um problema NP-completo?

1. AO problema da parada se tornaria decidível
2. BTodo problema em NP poderia ser resolvido em tempo polinomial, então P = NP
3. CTodos os algoritmos de tempo exponencial passariam imediatamente a rodar em tempo linear
4. DSó aquele problema passaria para P

2²ⁿ está em O(2ⁿ)?

1. ANão, porque 2²ⁿ cresce mais devagar que 2ⁿ
2. BSim, porque fatores constantes no expoente são sempre ignorados no O grande
3. CNão, porque 2²ⁿ = 4ⁿ e 4ⁿ / 2ⁿ = 2ⁿ cresce sem limite
4. DSim, porque ambos são exponenciais