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. AQuicksort
2. BBubble sort
3. CInsertion sort
4. DMerge sort

Quais são as três etapas de um algoritmo de divisão e conquista?

1. AChutar, verificar, repetir
2. BLer, calcular, escrever
3. COrdenar, buscar, retornar
4. DDividir, conquistar, combinar

Qual é a complexidade de tempo do insertion sort no pior caso?

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

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

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

Qual é a complexidade de tempo de multiplicar duas matrizes n × n com o laço triplo padrão?

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

Por que a base do logaritmo costuma ser omitida no O grande, como em O(log n)?

1. AA base só importa para n pequeno
2. BOs logaritmos são sempre arredondados para inteiros
3. CTodos os logaritmos em computação têm base 10, então ela fica implícita
4. DLogaritmos de bases diferentes diferem apenas por um fator constante

Qual é a complexidade de tempo de: for i = 1 to n: for (j = i; j ≤ n; j = j + i) faça trabalho O(1)?

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

Qual afirmação sobre P e NP está correta?

1. ATodo problema em P também está em NP
2. BFoi provado que P ≠ NP
3. CSoluções de problemas NP não podem ser verificadas rapidamente
4. DNP significa "não polinomial"